Insert into a BST

Difficulty: Medium Source: NeetCode

Problem

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST. Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

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

Example 2: Input: root = [40,20,60,10,30,50,70], val = 25 Output: [40,20,60,10,30,50,70,null,null,25]

Constraints:

• The number of nodes in the tree is in the range [0, 10^4]
• -10^8 <= Node.val <= 10^8
• All the values Node.val are unique
• -10^8 <= val <= 10^8
• It’s guaranteed that val does not exist in the original BST

Prerequisites

Before attempting this problem, you should be comfortable with:

• BST Property — Values smaller than a node go left, larger go right
• Recursion — Building the new tree by returning updated subtrees
• Pointer Manipulation — Attaching a new node at the correct leaf position

1. Recursive Insertion

Intuition

Follow the BST property to find where the new value belongs. When you reach a null position, that’s where the new node goes. The recursive version elegantly handles this by returning a new node when at null, which gets assigned to the parent’s left or right pointer.

Algorithm

1. If root is null, create and return a new node with val
2. If val < root.val, recurse left and assign the result to root.left
3. If val > root.val, recurse right and assign the result to root.right
4. Return root

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def insert_into_bst_recursive(root, val):
    if not root:
        return TreeNode(val)  # Found the insertion spot

    if val < root.val:
        root.left = insert_into_bst_recursive(root.left, val)
    else:
        root.right = insert_into_bst_recursive(root.right, val)

    return root

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

def inorder(root):
    """Inorder of a BST gives sorted order."""
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# --- tests ---
root1 = build_tree([4, 2, 7, 1, 3])
root1 = insert_into_bst_recursive(root1, 5)
print(inorder(root1))  # [1, 2, 3, 4, 5, 7]

root2 = build_tree([40, 20, 60, 10, 30, 50, 70])
root2 = insert_into_bst_recursive(root2, 25)
print(inorder(root2))  # [10, 20, 25, 30, 40, 50, 60, 70]

root3 = build_tree([])
root3 = insert_into_bst_recursive(root3, 5)
print(inorder(root3))  # [5]

Complexity

• Time: O(h) — traverse one path from root to insertion point
• Space: O(h) — recursion stack depth

2. Iterative Insertion

Intuition

Walk down the tree keeping track of the current node and its parent. When you fall off the tree (reach null), attach the new node to the parent at the correct side.

Algorithm

1. Handle empty tree edge case
2. Walk with curr pointer, comparing val to navigate left or right
3. When curr is null, we’ve found the insertion spot — attach to parent

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def insert_into_bst_iterative(root, val):
    new_node = TreeNode(val)

    if not root:
        return new_node

    curr = root
    while True:
        if val < curr.val:
            if not curr.left:
                curr.left = new_node
                break
            curr = curr.left
        else:
            if not curr.right:
                curr.right = new_node
                break
            curr = curr.right

    return root

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# --- tests ---
root1 = build_tree([4, 2, 7, 1, 3])
root1 = insert_into_bst_iterative(root1, 5)
print(inorder(root1))  # [1, 2, 3, 4, 5, 7]

root2 = build_tree([40, 20, 60, 10, 30, 50, 70])
root2 = insert_into_bst_iterative(root2, 25)
print(inorder(root2))  # [10, 20, 25, 30, 40, 50, 60, 70]

Complexity

• Time: O(h) — one path from root to leaf
• Space: O(1) — no recursion stack

Common Pitfalls

Forgetting to return root in the recursive version. The recursive function must return root at the end so the tree structure is preserved when you assign root.left = recurse(root.left, val).

Not handling the empty tree case. If root is null, just return the new node. Forgetting this causes a null pointer error.