Insert into a Binary Search Tree

Problem Statement: You have been given root node of a Binary Search Tree and a value. Your task is to insert value into Binary Search Tree. Return the root of the binary search tree after inserting that value such that the tree remains BST after insertion.
Note: There can be multiple ways of inserting a value into BST.

Example:

Input: root = [4, 2, 7, 1, 3], value = 5
Output: 1 2 3 4 5 7

Approach:

If the root is null then value is returned as new node.

If root.data is greater than given value, then it means the targeted value should be inserted in the left of the node so going to the left sub tree recursively.
else if the root.data is smaller than given value, then it means the targeted value should be inserted in the right of the node so goinf to the right sub tree recursively.
At last return the node.

Code Implementation:

Java

class Solution {

    static class Node {
        int data;
        Node left;
        Node right;

        // Constructor
        Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

    public static void main(String[] args) {
        /*
         * Creating Binary Search Tree The created BST is same as in the above given
         * figure (refer figure for reference)
         */
        Node root = new Node(4);
        root.left = new Node(2);
        root.right = new Node(7);
        root.left.left = new Node(1);
        root.left.right = new Node(3);

        /* this value is to be inserted into BST */
        int value = 5;

        /* calling method */
        insertIntoBST(root, value);

        /*
         * inOrder Traversal to check whether we have inserted the value
         * at its right position or not. If the sequence of values is in
         * sorted order then the value is inserted at its right position
         * and tree is BST otherwise not.
         */

        inorderTraversal(root);
    }

    public static Node insertIntoBST(Node root, int value) {
        /* return the value as new tree node */
        if (root == null) {
            return new Node(value);
        }

        /*
         * indicates that the value should lie in the left so traversing to the left of
         * tree
         */
        if (root.data > value) {
            root.left = insertIntoBST(root.left, value);
        }

        /*
         * indicates that the value should lie in the right so traversing to the right of
         * tree
         */
        if (root.data < value) {
            root.right = insertIntoBST(root.right, value);
        }

        return root;
    }

    private static void inorderTraversal(Node root) {
        if (root == null)
            return;

        // left
        inorderTraversal(root.left);

        // printing current root value
        System.out.print(root.data + " ");

        // right
        inorderTraversal(root.right);
    }
}

Output:

1 2 3 4 5 7

Complexity Analysis:

Time Complexity: O(n), where n is the number of nodes in tree.

Space Complexity: Considering the stack space, if the tree is balanced then O(log n) and if tree is unbalanced then O(n).

If you want to contribute such articles to solutions2coding.com please click here. Thank you!