Insert into a Binary Search Tree Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple Atlassian Facebook Google Microsoft
algorithms Binary Search Tree coding Interview interviewprep LeetCode LeetCodeSolutionsViews 3236

In this problem, we are given the root node of a Binary Search Tree containing integer values and an integer value of a node that we have to add in the Binary Search Tree and return its structure. After inserting the element into the BST, we have to print its Inorder Traversal.

Example

Binary Search Tree:
 
    7
 
  /     \

3         10

        /

      8
Integer Value = 11
3 7 8 10 11
Binary Search Tree:
           5

         /

       4

     /

   3
Integer Value = 2
2 3 4 5

Explanation

Insert into a Binary Search Tree Leetcode Solution

Insert into a Binary Search Tree Leetcode Solution

Approach(Recursive)

In order to decide where should any given node be inserted in our Binary Search Tree, we must set up a path from the root to the corresponding node whose left/right child will be the given node.

We can solve this recursively by passing on the task from a problem to its sub-problem. In this case, inserting a new node into a tree means to insert it to either its left subtree or right subtree. The same idea also holds for any further subtrees. We need to set up a base case. When we reach a point where the root node of any subtree is NULL, it would mean that we have reached the end of the path to insert the target node. So, we return a new node address having node value as the given value. Binary Search Trees have a significant advantage to search for any arbitrary element in O(logN) time under average cases. So, in this case, we find the position of the new node to be inserted in efficient time.

Algorithm

  1. Create a function insertIntoBST() which returns the address of the root of BST after inserting the given node
  2. insertIntoBST() has two parameters: root of the tree and value of the node to be inserted
  3. The function will do the following:
    • If root is NULL, return a new tree node with value same as the given value
    • If the given value is greater than value of root node, then call the same problem to the right subtree and then return the root
      • root.right = insertIntoBST(root->right , value)
      • return root
    • Else search in the left subtree as:
      • root.left= insertIntoBST(root.left, value)
      • return root
  4. Print the inorder traversal of the Binary Search Tree

Implementation of Insert into a Binary Search Tree Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;
struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

void inorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    inorderTraversal(root->left);
    cout << root->value << " ";
    inorderTraversal(root->right);
    return;
}


BSTNode* insertIntoBST(BSTNode* root , int val)
{
    if(root == NULL)
        return new BSTNode(val);
    if(val > root->value)
    {
        root->right = insertIntoBST(root->right , val);
        return root;
    }
    root->left = insertIntoBST(root->left , val);
    return root;
}

int main()
{
    BSTNode* root = new BSTNode(7);
    root->left = new BSTNode(3);
    root->right = new BSTNode(10);
    root->right->left = new BSTNode(8);
    int val = 11;
    root = insertIntoBST(root , val);
    inorderTraversal(root);
    return 0;
}

Java Program

class BSTNode
{
    int value;
    BSTNode left , right;

    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class insert_into_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(7);
        root.left = new BSTNode(3);
        root.right = new BSTNode(10);
        root.right.left = new BSTNode(8);
        int val = 11;
        root = insertIntoBST(root , val);
        inorderTraversal(root);
    }

    static BSTNode insertIntoBST(BSTNode root , int val)
    {
        if(root == null)
            return new BSTNode(val);
        if(val > root.value)
        {
            root.right = insertIntoBST(root.right , val);
            return root;
        }
        root.left = insertIntoBST(root.left , val);
        return root;
    }

    static void inorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        inorderTraversal(root.left);
        System.out.print(root.value + " ");
        inorderTraversal(root.right);
        return;
    }
}

3 7 8 10 11

Complexity Analysis of Insert into a Binary Search Tree Leetcode Solution

Time Complexity

O(H) = Height of BST = logN (where N = number of nodes in BST) in average cases(as we make logN recursive calls). But O(N) in the worst case when the tree is a skewed one. Because in case the tree is skewed, the search becomes a linear one.

Space complexity

O(H) in average cases. O(N) in the worst case. The case with Space Complexity is same as Time Complexity here as it depends on the number of recursive calls we make.

Approach(Iterative)

We can follow the above approach iteratively to improve on space complexity. Recursion uses stack frames which consume memory. So, in the iterative solution, we prevent the recursive call load and go down the tree on our search path until we strike a node whose either of left or right is NULL. When we have root.left/root.right= NULL, we set this node equal to a new node with value same as the given value. Note that we decide the path by comparing the values with root value in every recursion call.

Algorithm

  1. We again have a insertIntoBST() for the same purpose as above
  2. If the root is NULL
    1. return new node with value same as the given value
  3. Create a copy of root, say dummy to manipulate the content of BST
  4. While dummy is not NULL
    1. if given value is greater than root.val
      1. If root.right is NULL
        1. root.right = new node with given value
        2. return root
      2. Else, set
        1. root = root.right, to jump to right subtree
    2. Else if the value is less than or equal to root.val
      1. If root.left is NULL
        1. root.left = new node with given value
        2. return root
      2. Else, set
        1. root = root.left, to jump to left subtree
  5. Print the Inorder traversal of the BST

Implementation of Insert into a Binary Search Tree Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;
struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

void inorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    inorderTraversal(root->left);
    cout << root->value << " ";
    inorderTraversal(root->right);
    return;
}

BSTNode* insertIntoBST(BSTNode* root , int val)
{
    if(root == NULL)
        return new BSTNode(val);
    BSTNode* dummy = root;
    while(dummy != NULL)
    {
        if(val > dummy->value)
        {
            if(dummy->right == NULL)
            {
                dummy->right = new BSTNode(val);
                return root;
            }
            else
                dummy = dummy->right;
        }
        else
        {
            if(dummy->left == NULL)
            {
                dummy->left = new BSTNode(val);
                return root;
            }
            else
                dummy = dummy->left;
        }
    }
    return root;
}

int main()
{
    BSTNode* root = new BSTNode(7);
    root->left = new BSTNode(3);
    root->right = new BSTNode(10);
    root->right->left = new BSTNode(8);
    int val = 11;
    root = insertIntoBST(root , val);
    inorderTraversal(root);
    return 0;
}

Java Program

class BSTNode
{
    int value;
    BSTNode left , right;

    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class insert_into_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(7);
        root.left = new BSTNode(3);
        root.right = new BSTNode(10);
        root.right.left = new BSTNode(8);
        int val = 11;
        root = insertIntoBST(root , val);
        inorderTraversal(root);
    }

    static BSTNode insertIntoBST(BSTNode root , int val)
    {
        if(root == null)
            return new BSTNode(val);
        BSTNode dummy = root;
        while(dummy != null)
        {
            if(val > dummy.value)
            {
                if(dummy.right == null)
                {
                    dummy.right = new BSTNode(val);
                    return root;
                }
                else
                    dummy = dummy.right;
            }
            else
            {
                if(dummy.left == null)
                {
                    dummy.left = new BSTNode(val);
                    return root;
                }
                else
                    dummy = dummy.left;
            }
        }
        return root;
    }

    static void inorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        inorderTraversal(root.left);
        System.out.print(root.value + " ");
        inorderTraversal(root.right);
        return;
    }
}

3 7 8 10 11

Complexity Analysis of Insert into a Binary Search Tree Leetcode Solution

Time Complexity

O(H) = Height of BST = logN (where N = number of nodes in BST) in average cases. But O(N) in the worst case when the tree is a skewed one. Again, the time complexity is dependent on the number of iterations we make to reach to the destination after which the given node should be inserted and it depends on the tree stucture.

Space complexity

O(1). Even in the worst case, we only use constant space for variables.

Translate »