Insert into a Binary Search Tree

Link: LeetCode - Insert into a Binary Search Tree

Problem Statement

You are given the root of a binary search tree (BST) and an integer val.
Insert val into the BST such that its properties remain valid.
Return the root node of the BST after insertion.

Note: There may be multiple valid ways for the insertion, as long as the BST property is maintained.

Example

Input:

root = [4,2,7,1,3], val = 5

Output:

[4,2,7,1,3,5]

Constraints

• The number of nodes in the tree will be in the range [0, 10⁴].

• -10⁸ <= Node.val <= 10⁸

• All the values of the tree are unique.

• -10⁸ <= val <= 10⁸

Intuition

To insert a node in a Binary Search Tree, we:

• Traverse the tree starting from the root.

• Compare the val with current node:

  • If val < node.val: go to the left subtree.

  • If val > node.val: go to the right subtree.

• Once we reach a null pointer, we insert the node there.

Approach 1: Recursive

Java Code

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        // Base case: place the node here
        if (root == null) {
            return new TreeNode(val);
        }

        // If value is less, insert into left subtree
        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        } 
        // If value is greater, insert into right subtree
        else {
            root.right = insertIntoBST(root.right, val);
        }

        return root;
    }
}

Time and Space Complexity

• Time Complexity: O(H)
  Where H is the height of the BST

  • Balanced BST: O(log N)

  • Skewed BST: O(N)

• Space Complexity: O(H) due to recursion stack

Dry Run

Tree:

    4
   / \
  2   7
 / \
1   3

val = 5

• 5 > 4 → go right

• 5 < 7 → go left (left of 7 is null)

• Insert 5 there

Result:

    4
   / \
  2   7
 / \  /
1   3 5

Conclusion

Recursive insertion into a BST ensures we maintain all BST properties.
This problem is a great foundation for deeper BST operations like deletion and balancing.