Insert a Given Node in Binary Search Tree

Problem Statement: Given a root node reference of a Binary Search Tree and a key, insert a new node with value as the given key in the Binary Search Tree following the rules of a BST. Return the modified Binary Search Tree after insertion.

Examples

Example 1:

Input Format

Binary Search Tree: 4 2 7 1 3 -1 -1

Key to be Inserted: 5

Output

Modified Binary Search Tree: 4 2 7 1 3 5 -1

Or 

Modified Binary Search Tree: 5 4 7 3 -1 -1 -1 1 3

Or 

Modified Binary Search Tree: 4 2 5 1 3 -1 7

Explanation

After inserting a new node with value, there are multiple binary search trees possible. In the original binary search tree, the node with value 5 can be inserted as the left child of 7 or right child of 4 or can also become the root of the modified tree. These variations occur because there are multiple nodes with values that allow 5 to be inserted either on their left or right side, maintaining the Binary Search Tree properties.

Example 2:

Input Format: 

Binary Search Tree: 6 3 8 2 4 7 -1

Key to be Inserted: 5

Output: 

Modified Binary Search Tree: 6 3 8 2 4 7 -1 -1 -1 -1 5 -1 -1

Or

Modified Binary Search Tree: 6 5 8 3 -1 7 -1 3 2 -1 -1

Explanation

After inserting a new node with value, there are multiple binary search trees possible. In the original binary search tree, the node with value 5 can be inserted as the right child of 4 or left child of root 6. These variations occur because there are multiple nodes with values that allow 5 to be inserted either on their left or right side, maintaining the Binary Search Tree properties.

Practice:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach: 

Algorithm:

Step 1: Traverse the tree to Determine the Insertion Point

Compare the value to be inserted with the current node’s value. If the value is less than the current node’s value, move to the left subtree. If the value is greater than the current node’s value, move to the right subtree. Repeat this process until finding a potential leaf (a null child) in the appropriate subtree.

Step 2: Insert a new node with the given value

Create a new node with the given value. Attach this new node as a child to the parent node at the empty spot found in the previous step. If the value is less than the parent’s node value, attach as the left child; otherwise, attach as the right child.

Step 3: Return the modified Binary Search Tree.

Code:

C++ Code

#include <iostream>
using namespace std;

// Definition of TreeNode structure
// for a binary tree node
struct TreeNode {
    // Value of the node
    int val;    
    
    // Pointer to the left child node
    TreeNode* left; 
    // Pointer to the right child node
    TreeNode* right;

    // Constructor to initialize the node with a
    // value and set left and right pointers to null
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        // If the root node is NULL, create a new node
        // with the given value and return it as the new root.
        if(root==NULL){
            return new TreeNode(val);
        }
        
        // cur pointer to traverse the tree
        TreeNode* cur = root;
        
        // While loop to traverse the tree to find
        // the appropriate position for insertion.
        while(true){
            // If the current node's value is less
            // than or equal to the value to be inserted,
            // move to the right subtree.
            if(cur->val <= val){
                // If the right child of the current node
                // is not NULL, update 'cur' to the right child.
                if(cur->right !=NULL){
                    cur = cur->right;
                }
                // If the right child is NULL, create a new node
                // with the given value as the right child
                // and exit the while loop.
                else{
                    cur->right = new TreeNode(val);
                    break;
                }
            }
            // If the current node's value is greater than
            // the value to be inserted,
            // move to the left subtree.
            else{
                // If the left child of the current node
                // is not NULL, update 'cur' to the left child.
                if(cur->left !=NULL){
                    cur = cur->left;
                }
                // If the left child is NULL, create a new node
                // with the given value as the left child
                // and exit the while loop.
                else{
                    cur->left = new TreeNode(val);
                    break;
                }
            }
        }
        // Return the root of the
        // modified tree after insertion.
        return root;
    }
};



// Function to perform an in-order traversal
// of a binary tree and print its nodes
void printInOrder(TreeNode* root) {
    // Check if the current node
    // is null (base case for recursion)
    if (root == NULL) {
        // If null, return and
        // terminate the function
        return; 
    }

    // Recursively call printInOrder
    // for the left subtree
    printInOrder(root->left);
    
    // Print the value of the current node
    cout << root->val << " ";

    // Recursively call printInOrder
    // for the right subtree
    printInOrder(root->right);
}


int main() {
    Solution solution;

    // Creating a sample tree 
    TreeNode* root = new TreeNode(6);
    root->left = new TreeNode(3);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(7);

    // Printing the original tree
    cout << "Original Tree (Inorder Traversal): ";
    printInOrder(root);
    cout << endl;

    int keyToInsert = 5;
    TreeNode* updatedTree = solution.insertIntoBST(root, keyToInsert);

    cout << "Tree After Insertion (Inorder Traversal): ";
    printInOrder(updatedTree);
    cout << endl;

    return 0;
}

Output:

Original Tree (Inorder Traversal): 2 3 4 6 7 8

Tree After Insertion (Inorder Traversal): 2 3 4 5 6 7 8

Time Complexity: O(log N) because of the logarithmic height of the Binary Search Tree that is traversed during the insertion process.

Space Complexity: O(1) as no additional data structures or memory allocation is done

Java Code

class TreeNode {
    // Value of the node
    int val;
    // Pointer to the left child node
    TreeNode left;
    // Pointer to the right child node
    TreeNode right;

    // Constructor to initialize the node with a value
    // and set left and right pointers to null
    TreeNode(int x) {
        val = x;
        left = null;
        right = null;
    }
}

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        // If the root node is null, create a new node
        // with the given value and return it as the new root
        if (root == null) {
            return new TreeNode(val);
        }

        // cur pointer to traverse the tree
        TreeNode cur = root;

        // While loop to traverse the tree to find
        // the appropriate position for insertion
        while (true) {
            // If the current node's value is less
            // than or equal to the value to be inserted,
            // move to the right subtree
            if (cur.val <= val) {
                // If the right child of the current node
                // is not null, update 'cur' to the right child
                if (cur.right != null) {
                    cur = cur.right;
                }
                // If the right child is null, create a new node
                // with the given value as the right child
                // and exit the while loop
                else {
                    cur.right = new TreeNode(val);
                    break;
                }
            }
            // If the current node's value is greater than
            // the value to be inserted,
            // move to the left subtree
            else {
                // If the left child of the current node
                // is not null, update 'cur' to the left child
                if (cur.left != null) {
                    cur = cur.left;
                }
                // If the left child is null, create a new node
                // with the given value as the left child
                // and exit the while loop
                else {
                    cur.left = new TreeNode(val);
                    break;
                }
            }
        }
        // Return the root of the modified tree after insertion
        return root;
    }
}

public class Main {
    // Function to perform an in-order traversal
    // of a binary tree and print its nodes
    public static void printInOrder(TreeNode root) {
        // Check if the current node is null
        // (base case for recursion)
        if (root == null) {
            // If null, return and terminate the function
            return;
        }

        // Recursively call printInOrder for the left subtree
        printInOrder(root.left);

        // Print the value of the current node
        System.out.print(root.val + " ");

        // Recursively call printInOrder for the right subtree
        printInOrder(root.right);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // Creating a sample tree
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(3);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(7);

        // Printing the original tree
        System.out.print("Original Tree (Inorder Traversal): ");
        printInOrder(root);
        System.out.println();

        int keyToInsert = 5;
        TreeNode updatedTree = solution.insertIntoBST(root, keyToInsert);

        System.out.print("Tree After Insertion (Inorder Traversal): ");
        printInOrder(updatedTree);
        System.out.println();
    }
}

Output:

Original Tree (Inorder Traversal): 2 3 4 6 7 8

Tree After Insertion (Inorder Traversal): 2 3 4 5 6 7 8

Time Complexity: O(log N) because of the logarithmic height of the Binary Search Tree that is traversed during the insertion process.

Space Complexity: O(1) as no additional data structures or memory allocation is done

Python Code

# Definition of TreeNode class for a binary tree node
class TreeNode:
    # Constructor to initialize the node with a value
    # and set left and right pointers to None
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# Solution class with insertIntoBST method
class Solution:
    def insertIntoBST(self, root, val):
        # If the root node is None, create a new node
        # with the given value and return it as the new root.
        if not root:
            return TreeNode(val)
        
        # cur pointer to traverse the tree
        cur = root
        
        # While loop to traverse the tree to find
        # the appropriate position for insertion.
        while True:
            # If the current node's value is less
            # than or equal to the value to be inserted,
            # move to the right subtree.
            if cur.val <= val:
                # If the right child of the current node
                # is not None, update 'cur' to the right child.
                if cur.right:
                    cur = cur.right
                # If the right child is None, create a new node
                # with the given value as the right child
                # and exit the while loop.
                else:
                    cur.right = TreeNode(val)
                    break
            # If the current node's value is greater than
            # the value to be inserted,
            # move to the left subtree.
            else:
                # If the left child of the current node
                # is not None, update 'cur' to the left child.
                if cur.left:
                    cur = cur.left
                # If the left child is None, create a new node
                # with the given value as the left child
                # and exit the while loop.
                else:
                    cur.left = TreeNode(val)
                    break
        
        # Return the root of the
        # modified tree after insertion.
        return root


# Function to perform an in-order traversal
# of a binary tree and print its nodes
def printInOrder(root):
    # Check if the current node
    # is None (base case for recursion)
    if not root:
        # If None, return and
        # terminate the function
        return

    # Recursively call printInOrder
    # for the left subtree
    printInOrder(root.left)
    
    # Print the value of the current node
    print(root.val, end=" ")
    
    # Recursively call printInOrder
    # for the right subtree
    printInOrder(root.right)


def main():
    solution = Solution()

    # Creating a sample tree 
    root = TreeNode(6)
    root.left = TreeNode(3)
    root.right = TreeNode(8)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(4)
    root.right.left = TreeNode(7)

    # Printing the original tree
    print("Original Tree (Inorder Traversal): ", end="")
    printInOrder(root)
    print()

    keyToInsert = 5
    updatedTree = solution.insertIntoBST(root, keyToInsert)

    print("Tree After Insertion (Inorder Traversal): ", end="")
    printInOrder(updatedTree)
    print()


if __name__ == "__main__":
    main()

Output:

Original Tree (Inorder Traversal): 2 3 4 6 7 8

Tree After Insertion (Inorder Traversal): 2 3 4 5 6 7 8

Time Complexity: O(log N) because of the logarithmic height of the Binary Search Tree that is traversed during the insertion process.

Space Complexity: O(1) as no additional data structures or memory allocation is done

JavaScript Code

// Definition of TreeNode structure
// for a binary tree node
class TreeNode {
    // Constructor to initialize
    // the node with a value
    constructor(x) {
        this.val = x;
        // Pointer to the left child node
        this.left = null; 
        // Pointer to the right child node
        this.right = null; 
    }
}

class Solution {
    insertIntoBST(root, val) {
        // If the root node is null, create a new node
        // with the given value and return it as the new root.
        if (root === null) {
            return new TreeNode(val);
        }

        // cur pointer to traverse the tree
        let cur = root;

        // While loop to traverse the tree to find
        // the appropriate position for insertion.
        while (true) {
            // If the current node's value is less than
            // or equal to the value to be inserted,
            // move to the right subtree.
            if (cur.val <= val) {
                // If the right child of the current node
                // is not null, update 'cur' to the right child.
                if (cur.right !== null) {
                    cur = cur.right;
                }
                // If the right child is null, create a
                // new node with the given value as the
                // right child and exit the loop.
                else {
                    cur.right = new TreeNode(val);
                    break;
                }
            }
            // If the current node's value is greater than the
            // value to be inserted, move to the left subtree.
            else {
                // If the left child of the current node is not
                // null, update 'cur' to the left child.
                if (cur.left !== null) {
                    cur = cur.left;
                }
                // If the left child is null, create a
                // new node with the given value as the
                // left child and exit the loop.
                else {
                    cur.left = new TreeNode(val);
                    break;
                }
            }
        }
        // Return the root of the
        // modified tree after insertion.
        return root;
    }
}

// Function to perform an in-order traversal
// of a binary tree and print its nodes
function printInOrder(root) {
    // Check if the current node is null
    // (base case for recursion)
    if (root === null) {
        // If null, return and
        // terminate the function
        return;
    }

    // Recursively call printInOrder
    // for the left subtree
    printInOrder(root.left);

    // Print the value of the current node
    console.log(root.val + " ");

    // Recursively call printInOrder
    // for the right subtree
    printInOrder(root.right);
}

// Creating a sample tree
let root = new TreeNode(6);
root.left = new TreeNode(3);
root.right = new TreeNode(8);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(7);

// Printing the original tree
console.log("Original Tree (Inorder Traversal): ");
printInOrder(root);
console.log("\n");

let keyToInsert = 5;
let solution = new Solution();
let updatedTree = solution.insertIntoBST(root, keyToInsert);

console.log("Tree After Insertion (Inorder Traversal): ");
printInOrder(updatedTree);
console.log("\n");

Output:

Original Tree (Inorder Traversal): 2 3 4 6 7 8

Tree After Insertion (Inorder Traversal): 2 3 4 5 6 7 8

Time Complexity: O(log N) because of the logarithmic height of the Binary Search Tree that is traversed during the insertion process.

Space Complexity: O(1) as no additional data structures or memory allocation is done

In case you are learning DSA, you should definitely check out our free A2Z DSA Course with videos and blogs.

Special thanks to Gauri Tomar for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article