parent in a binary search tree

This is a discussion on parent in a binary search tree within the C Programming forums, part of the General Programming Boards category; I have this program where in want to delete a node in a BST. But before i delete that node ...

  1. #1
    Registered User
    Join Date
    Jun 2009
    Location
    US of A
    Posts
    305

    parent in a binary search tree

    I have this program where in want to delete a node in a BST. But before i delete that node i must find its parent. Now what is happening currently is that i reach the parent but as i am in a recursive loop i am unable to figure out why the program does not terminate when i have found a parent.

    [insert]
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct node
    {
    	struct node *left;
    	int data;
    	struct node *right;
    };
    
    void insert(struct node **root, int data);
    void search(struct node** root, int data);
    struct node * searchloc(struct node **root, int data);
    void delete(struct node **root, int data);
    struct node * searchparent(struct node **root, struct node *temp);
    struct node * inorder(struct node *root, struct node *temp);
    
    int main(void)
    {
    
    	//printf("\n %d", SIZE);
    	struct node *root = NULL;
    	int data;
    	char ch;
    
    	do
    	{
    		printf("\n Enter the data\n");
    		scanf("%d", &data);
    		insert(&root, data);
    		printf("\n Do you want to add more elements\n");
    		scanf("\n%c", &ch);
    	}while(ch == 'y' || ch == 'Y');
    
    	printf("\n Do you want to search data");
    	scanf("\n %c", &ch);
    	while(ch == 'y' || ch == 'Y')
    	{
    	printf("\n Enter the data to search in the BST");
    	scanf("\n %d", &data);
    	search(&root, data);
    	printf("\n Do you want to search data");
    	scanf("\n %c", &ch);
    	}
    
    	delete(&root, 8);
    	return 0;
    }
    
    void delete(struct node **root, int data)
    {
    	struct node *temp = NULL;
    	struct node ** r;
    	struct node *parent;
    	struct node *insuc;
    
    	r = root;
    	// find where is the data that is get the address
    	temp = searchloc(r, data);
    
    	if(temp != NULL)
    			printf("\n Location at which element was found is %p", temp);
    	else
    	{
    		printf("\n The data that you tried to delete doesnt exist in the list");
    		return;
    	}
    
    	r = root;
    	// get the parents address as well
    	parent = searchparent(*r, temp);
    
    	if(parent != NULL)
    		printf("\n Location at which parent was found is %p", parent);
    
    	// the location where the element has been found has no children
    	// simply delete the element and move ahead
    	if(temp->left == NULL && temp->right == NULL)
    	{
    		// set the pointer in the parent to null
    		if(parent->left == temp)
    			parent->left = NULL;
    		else if (parent->right == temp)
    			parent->right = NULL;
    
    		free(temp);
    	}
    
    	// the location where the element has been found has one children
    	// set the pointer in the parent to point to the child
    	if(temp->left == NULL && temp->right != NULL)
    	{
    		if(parent->left == temp)
    			parent->left = temp->right;
    		else if(parent->right == temp)
    			parent->right = temp->right;
    
    		free(temp);
    		return;
    	}
    	else if(temp->left != NULL && temp->right == NULL)
    	{
    		if(parent->left == temp)
    			parent->left = temp->left;
    		else if(parent->right == temp)
    			parent->right = temp->left;
    
    		free(temp);
    		return;
    	}
    
    	// the location where the element has been found has two children
    	// 1. Find the inorder successor
    	// 2. Copy its data to the node being deleted
    	// 3. The inorder successor will always have one or no child
    	// which reduces the problem to deletion of a node with one or zero child
    
    	if(temp->left != NULL && temp->right != NULL)
    	{
    		// find the location of the inorder successor
    		insuc =	inorder(root, temp);
    		printf("\n Location of inorder successor is %p and its value is %d", insuc, insuc->data);
    	}
    }
    
    struct node * inorder(struct node **root, struct node *temp)
    {
    	int i = 0;
    	if((*root) != NULL)
    	{
    		inorder((*root)->left, temp);
    		if(temp->data == (*root)->data)
    		{
    			printf("\n %d", (*root)->data);
    			++ i;
    		}
    		// next time i come here with value of i being 1 i would have got the inorder successor 
    		else
    		{
    			if(i == 1)
    			{
    				return (*root);
    			}
    			else
    				printf("\n Still searching");
    		}
    		inorder((*root)->right, temp);
    	}
    }
    
    struct node * searchparent(struct node *root, struct node *temp)
    {
    	if(root->left != NULL && root->left == temp)
    	{
    		return root;
    	}
    	else if(root->left != NULL)
    	{
    		searchparent(root->left, temp);
    		if(root->right != NULL)
    			searchparent(root->right, temp);
    	}
    
        if(root->right != NULL && root->right == temp)
    	{
    		return root;
    	}
    	else if(root->left != NULL)
    	{
    		searchparent(root->left, temp);
    		if(root->right != NULL)
    			searchparent(root->right, temp);
    	}
    }
    
    struct node * searchloc(struct node **root, int data)
    {
    
    	if((*root)->data == data)
    	{
    		printf("\n Data Found in the tree");
    		return (*root);
    	}
    	// search in the left of the root
    	else if((*root)->data < data)
    	{
    		if((*root)->right != NULL)
    		{
    			searchloc(&(*root)->right, data);
    		}
    		else
    		{
    			printf("\n Data not in the tree");
    			return NULL;
    		}
    	}
    	// search in the right of the root
    	else if((*root)->data > data)
    	{
    		if((*root)->left != NULL)
    		{
    		searchloc(&(*root)->left, data);
    		}
    		else
    		{
    			printf("\n Data not in the tree");
    			return NULL;
    		}
    	}
    	else
    	{
    		printf("\n Data does not exist in the tree");
    		return NULL;
    	} 
    
    }
    
    
    void search(struct node** root, int data)
    {
    	if((*root)->data == data)
    	{
    		printf("\n Data Found in the tree");
    		return;
    	}
    	// search in the left of the root
    	else if((*root)->data < data)
    	{
    		if((*root)->right != NULL)
    		{
    			search(&(*root)->right, data);
    		}
    		else
    		{
    			printf("\n Data not in the tree");
    			return;
    		}
    	}
    	// search in the right of the root
    	else if((*root)->data > data)
    	{
    		if((*root)->left != NULL)
    		{
    		search(&(*root)->left, data);
    		}
    		else
    		{
    			printf("\n Data not in the tree");
    			return;
    		}
    	}
    	else
    	{
    		printf("\n Data does not exist in the tree");
    		return;
    	} 
    }
    
    void insert(struct node **root, int data)
    {
    	
    	struct node *temp;
    
    	// check if its the first element that i am going to add
    	if(*root == NULL)
    	{
    		*root = (struct node *) malloc(sizeof(struct node));
    		(*root)->left = NULL;
    		(*root)->right = NULL;
    		(*root)->data = data;
    		return;
    	}
    	// this is not the first element
    	// find its correct place in the tree
    	// data is larger than root so put in the right
    	else
    	{
    		if((*root)->data < data)
    		{
    			insert(&((*root)->right), data);
    		}
    	
    		else if((*root)->data > data)
    		{
    			insert(&((*root)->left), data);
    		}
    	}
    }

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    The program you posted doesn't even compile. Perhaps you should fix those problems first?

    test.c: In function `delete':
    test.c:71: warning: passing arg 1 of `searchparent' from incompatible pointer type
    test.c:121: warning: passing arg 1 of `inorder' from incompatible pointer type
    test.c: At top level:
    test.c:127: error: conflicting types for 'inorder'
    test.c:16: error: previous declaration of 'inorder' was here
    test.c:127: error: conflicting types for 'inorder'
    test.c:16: error: previous declaration of 'inorder' was here
    test.c: In function `inorder':
    test.c:131: warning: passing arg 1 of `inorder' from incompatible pointer type
    test.c:147: warning: passing arg 1 of `inorder' from incompatible pointer type
    test.c: At top level:
    test.c:152: error: conflicting types for 'searchparent'
    test.c:15: error: previous declaration of 'searchparent' was here
    test.c:152: error: conflicting types for 'searchparent'
    test.c:15: error: previous declaration of 'searchparent' was here

  3. #3
    Registered User
    Join Date
    Jun 2009
    Location
    US of A
    Posts
    305
    It compiles fine without giving any error.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by roaan View Post
    It compiles fine without giving any error.
    If you fix line 152 so that it agrees with the prototype, then yes it will compile. (If you don't, it won't.) Why do you left, then right, then left, then right in your searchparent? For that matter, don't you know which way to go? (If temp->data is bigger than root->data, go right, if it's smaller, go left.)

  5. #5
    Registered User
    Join Date
    Jun 2009
    Location
    US of A
    Posts
    305
    Oh yes you were right. But then i dont know why my Visual Studio compiles everything. I posted the problem in another thread as well.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 08:11 AM
  2. Binary Tree Search
    By nickname_changed in forum C++ Programming
    Replies: 7
    Last Post: 01-12-2004, 11:40 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 03:53 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21