CODEWITHSUNDEEP
c++recursionbinary-search-tree
chota bheem
chota bheem

Reputation: 411

BST-Insertion explaination

I was trying to learn Binary search tree,I have one doubt related to BST insertion.This is not my code I have taken this from http://cslibrary.stanford.edu/110/BinaryTrees.html 

struct node* insert(struct node* node, int data) { 
  // 1. If the tree is empty, return a new, single node 
  if (node == NULL) { 
    return(newNode(data)); 
  } 
  else { 
    // 2. Otherwise, recur down the tree 
    if (data <= node->data) node->left = insert(node->left, data); 
    else node->right = insert(node->right, data);

    return(node); // return the (unchanged) node pointer-->THIS LINE
  } 
}

My doubt As mentioned in the code I don't understand that why root doesn't get changed on insertion(last line).Why it is the same root everytime ?

Upvotes: 0

Views: 65

Answers (2)

Mohamed Fouad
Mohamed Fouad

Reputation: 111

recursive call in this code doesn't affect root node because you send root node at first time ( at that time root is NULL) and will enter the if condition otherwise will not affect root consider the following tree and call

 2 --  (call insert and gave it root node, data -4)
   / \
  1   10
     /
    5

first call will check if root == NULL ---this if false will test whatever -4 greater or smaller than 2 and will make recursive call on left node

    2 
   / \
  1-- 10  (call insert and gave it left child of root node, data -4)
     /
    5

and this node again not NULL will make anther recursive call of left of left of root this node is NULL

 2 
   / \
  1  10 
 /   /
NULL 5  (call insert and gave it left child of left child root node, data -4)

here will create new node and with returning will assign this node to left of left of root and return pointer on it to first call 

    2 
   / \
  1  10 
 /   /
-4   5

just ... my advice read about recursive functions good before studying BST

Upvotes: 1

Benjy Kessler
Benjy Kessler

Reputation: 7616

If you have a BST and want to insert the stream 3, 2, 8, 5, 7 you will do as follows:

  3

  3
 /
2

  3
 / \
2   8

  3
 / \
2   8
   /
  5

  3
 / \
2   8
   /
  5
   \
    7

As you can see the root never changes. Each element you insert gets added as a leaf in the correct position.

Upvotes: 0

Related Questions