Insert into a Binary Search Tree

1. Problem Summary

You are given:

the root of a Binary Search Tree (BST)
an integer val to insert

Your task is to insert val into the BST while maintaining BST properties and return the updated root.

Important points:

A BST satisfies: left subtree values < node.val < right subtree values
Insertion must follow the BST path rules
If tree is empty, val becomes the new root
No rebalancing required (not AVL or Red-Black)

Example:

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

Tree before:
      4
     / \
    2   7
   / \
  1   3

After insertion:
      4
     / \
    2   7
   / \  /
  1   3 5

2. Key Insights

Insight 1: BST insertion follows binary search direction

If:

val < node.val → go to left subtree
val > node.val → go to right subtree

Insight 2: Insert when null child encountered

When traversal reaches a null position, create new node.

Insight 3: No need to check for duplicates

Per classic BST structure:

duplicates are not inserted
this problem assumes no duplicate values appear

Insight 4: Recursive or iterative both valid

Recursive version is simpler and cleaner.

Insight 5: Must return root

Even though tree changes, root reference must be returned.

3. Approach

Recursive Insertion

Steps:

If root is null → return new node with val
If val < root.val:
- root.left = recursive insert into left subtree
Else:
- root.right = recursive insert into right subtree
Return root

4. Time and Space Complexity

Time Complexity:

O(H)

Where H = tree height
Worst case skewed tree: O(N)
Balanced tree: O(log N)

Space Complexity:

O(H)

Recursion stack depth matches tree height.

5. Java Solution (Recursive)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }

        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        } else {
            root.right = insertIntoBST(root.right, val);
        }

        return root;
    }
}

6. Iterative Version (No recursion)

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }

        TreeNode current = root;

        while (true) {
            if (val < current.val) {
                if (current.left == null) {
                    current.left = new TreeNode(val);
                    break;
                }
                current = current.left;
            } else {
                if (current.right == null) {
                    current.right = new TreeNode(val);
                    break;
                }
                current = current.right;
            }
        }

        return root;
    }
}

7. Dry Run Examples

Example 1

Input:

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

Traversal:

5 > 4 → go right
5 < 7 → go left
left child null → insert here

Output tree has 5 under 7.

Example 2

Input:

root = [], val = 10

Tree empty → new root created

Output:

[10]

Example 3

Input:

root = [8,5,12,3,7], val = 6

Path:
6 < 8 → left
6 > 5 → right
6 < 7 → left inserted

Output retains BST ordering.

Example 4

Input:

root = [1], val = 2

2 > 1 → insert right

Output:

[1,null,2]

Example 5

Input:

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

1 < 5 → left
1 < 3 → left
1 < 2 → left inserted

8. Why This Solution Works

Uses BST ordering property correctly
Finds exact insertion point
Never violates structure rules
Handles empty tree case
Preserves subtree references properly

9. Common Mistakes

Forgetting to return root at the end
Not assigning recursive result back to child pointer
Treating duplicates incorrectly
Attempting balancing (not required)
Modifying unrelated subtree pointers