Recursion for Coding Interviews in C++/

...

/

Insert Values in a Binary Search Tree

Insert Values in a Binary Search Tree

This lesson will help you learn recursion through trees.

We'll cover the following...

What is a Binary Search Tree?

A Binary Search Tree (BST) is a hierarchical data structure that consists of vertices connected through edges. The value of the left node is less than the parent node, and the value of the right node is greater than the parent node.

%0 node_1 6 node_1553672885624 4 node_1->node_1553672885624 node_3 8 node_1->node_3 node_1553672900128 2 node_1553672885624->node_1553672900128 node_1553673153245 5 node_1553672885624->node_1553673153245

Code Implementation

Below is the code implementation for

Press + to interact
#include <iostream>
using namespace std;
// Defining the TreeNode structure
struct TreeNode
{
  int value;
  TreeNode *left; 
  TreeNode *right;
};
// function just to make new Tree Node and allocate memory to it
TreeNode* newTreeNode(int data)
{
  TreeNode* temp = new TreeNode;
  temp->value = data;
  temp->left = NULL;
  temp->right = NULL;
  return temp;
}
//insert a Node in the Tree
void insert(TreeNode* &root, int data)
{
  //base case
  // inserts at a root if it is null
  if (root == NULL) 
  {
    root = newTreeNode(data);
    return;
  }
  
  // first recursive case
  //inserts recusrively to the left side of the node after comparing values 
  if (data<root->value)
  {
    insert(root->left,data); 
  }
  
  // second recursive cae
  //inserts recusrively to the right side of the node after comparing values 
  else
  {	
    insert(root->right, data); 
  }
}
// printing of tree using inorder traversal
void inorder(TreeNode* root)
{
  if (root == NULL)
  {
    return;
  }
  
  inorder(root->left);
  cout << root->value << " ";
  inorder(root->right);
}
// main function
int main()
{
  TreeNode* root = NULL;
  
  insert(root,6);
  insert(root,4);
  insert(root,8);
  insert(root,2);
  insert(root,5);
  
  inorder(root);
  return 0;
}

Understanding the Code

In the code above, the function insert is a recursive function as it makes a recursive call. Below is an explanation of the above code:

Driver Function

  • In the main() ...