insert_node_in_Binary_Search_Tree.txt

/*Insert a node in a binary search tree*/
/* 
 Helper function that allocates a new node 
 with the given data and NULL left and right 
 pointers. 
*/ 
struct node* NewNode(int data) { 
  struct node* node = new(struct node);    // "new" is like "malloc" 
  node->data = data; 
  node->left = NULL; 
  node->right = NULL;

  return(node); 
} 
 

/* 
 Give a binary search tree and a number, inserts a new node 
 with the given number in the correct place in the tree. 
 Returns the new root pointer which the caller should 
 then use (the standard trick to avoid using reference 
 parameters). 
*/ 
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 
  } 
} 

/*Reference:http://cslibrary.stanford.edu/110/BinaryTrees.html#csoln*/