Insert into a Binary Search Tree: Finding the Right Leaf

You are given the root of a binary search tree and a value to insert. Add a new node with that value to the tree while maintaining the BST property, and return the root. The problem guarantees that the value does not already exist in the tree, and any valid insertion is accepted. This is LeetCode 701: Insert into a Binary Search Tree, and it is the natural companion to searching a BST. If you can navigate the tree to find where a value would live, you can insert it there.

Why this problem matters

Insertion is one of the three core BST operations, alongside search and deletion. While search just navigates the tree and reports what it finds, insertion takes that same navigation and attaches a new node at the end of the path. If you already understand how BST search works, insertion is a small step forward. You follow the exact same left-or-right decision at each node, but instead of returning "not found" when you hit a null child, you create a new node and attach it.

This problem also reinforces a key property of BSTs: the structure is determined by the order in which values are inserted. Inserting the same set of values in a different order produces a different tree shape, but all of them are valid BSTs. The problem says any valid result is acceptable, so inserting at a leaf position is the simplest and most natural approach.

Understanding insertion is also a prerequisite for understanding deletion. When you delete a node with two children, one common technique is to replace it with its inorder successor, which is effectively a combination of search and insertion logic. Getting insertion down cold makes deletion much easier to reason about.

Recursive approach

The recursive approach mirrors BST search almost exactly. At each node, you compare the value to insert against the current node's value. If the value is smaller, you recurse into the left subtree. If it is larger, you recurse into the right subtree. When you reach a null node, you have found the insertion point, so you create and return a new node.

The key insight is that the recursive call returns the (possibly updated) subtree. When you reach null, you return the new node. The parent then attaches that new node as its left or right child through the assignment node.left = insert(node.left, val) or node.right = insert(node.right, val).

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

def insert_into_bst(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_into_bst(root.left, val)
    else:
        root.right = insert_into_bst(root.right, val)
    return root

Let's trace through inserting 6 into the tree [5, 3, 8, 1, 4]:

• insert(root=5, val=6): 6 > 5, so recurse right.
• insert(root=8, val=6): 6 < 8, so recurse left.
• insert(root=None, val=6): Base case. Return a new TreeNode(6).
• Back at node 8: node.left = TreeNode(6). Return node 8.
• Back at node 5: node.right = node 8 (unchanged). Return node 5.

The tree now has 6 as the left child of 8. The BST property holds because 6 > 5 (it is in the right subtree of 5) and 6 < 8 (it is in the left subtree of 8).

Iterative approach

The iterative approach uses a pointer to walk down the tree, keeping track of the parent node so you know where to attach the new node once you find a null spot. This avoids the overhead of recursive calls and makes the control flow explicit.

def insert_into_bst(root, val):
    new_node = TreeNode(val)
    if root is None:
        return new_node
    current = root
    while current:
        if val < current.val:
            if current.left is None:
                current.left = new_node
                return root
            current = current.left
        else:
            if current.right is None:
                current.right = new_node
                return root
            current = current.right
    return root

The logic is the same as the recursive version, just expressed as a loop. At each node, you decide whether to go left or right. If the child in that direction is null, you have found the spot and you attach the new node directly. If the child exists, you move the pointer down and repeat.

One small advantage of this approach is that it avoids the repeated return root through the call stack. The recursive version technically reassigns node.left or node.right at every level even though only the bottom level actually changes anything. The iterative version only writes once, at the exact insertion point.

Why insert at a leaf?

You might wonder whether there are other valid places to insert a new node. Technically, yes. You could restructure the tree so that the new value ends up as an internal node. But inserting at a leaf is by far the simplest approach, and the problem explicitly says any valid BST result is accepted.

Inserting at a leaf works because of the BST property itself. As you navigate down the tree, each comparison narrows the valid range for the new value. By the time you reach a null child, you know that the new value belongs exactly in that spot. Every ancestor above it has already been compared, and the BST ordering is maintained.

This is also the most efficient approach. You only visit nodes along a single root-to-leaf path, and you make exactly one structural change to the tree (attaching the new node). No rotations, no rebalancing, no restructuring. For a basic BST, this is all you need.

Complexity analysis

Time is O(h) for both approaches, where h is the height of the tree. You visit at most one node per level as you walk from the root to a leaf. For a balanced BST, h = log n. For a completely skewed tree (essentially a linked list), h = n.

Space differs between the two. The recursive approach uses O(h) space for the call stack. The iterative approach uses O(1) extra space since it only maintains a pointer. If you are working with very deep trees or care about stack overflow, the iterative version is safer.

Edge cases to watch for

• Empty tree (root is None): The new node becomes the root. Both approaches handle this as the base case.
• Insert the smallest value: You keep going left at every node until you reach a null left child. The new node becomes the leftmost leaf.
• Insert the largest value: You keep going right at every node until you reach a null right child. The new node becomes the rightmost leaf.
• Single node tree: You compare once, then attach as either the left or right child depending on the comparison.

The building blocks

BST insertion builds directly on BST search. The navigation logic is identical: compare the target value against the current node, go left if smaller, go right if larger. The only difference is what happens at the end. Search returns null or the matching node. Insertion creates a new node and attaches it.

This pattern of "navigate then act" shows up throughout tree problems. Inorder traversal uses the BST property to visit nodes in sorted order. Deletion uses the same navigation to find the node, then restructures the tree to remove it. If you internalize how the left-or-right decision at each node narrows your position in the tree, all of these operations become variations on the same theme.

The recursive structure here is also worth noting. The pattern of node.left = recurse(node.left, ...) is a common way to modify a tree in place while preserving the return-the-root convention. You will see this exact pattern in deletion, trimming, and other tree modification problems.

From understanding to recall

You have just worked through both recursive and iterative BST insertion, traced the algorithms step by step, and seen why inserting at a leaf is the natural choice. Right now, you can probably write either solution from scratch without hesitation.

But will you remember the details in two weeks? Will you remember that the recursive version returns the new node from the base case and lets the parent attach it? Will you remember that the iterative version checks for null before moving the pointer? These small details are easy to forget, and forgetting them means debugging during an interview instead of solving the problem confidently.

Spaced repetition locks these patterns in. You practice writing the insertion function from memory at increasing intervals, and each repetition strengthens the neural pathways. After a few reps, the recursive base case and the left-or-right branching become automatic. You stop thinking about the mechanics and start thinking about higher-level strategy.

Related posts

• Search in a Binary Search Tree - Uses the same left-or-right navigation but without modifying the tree, the natural prerequisite for insertion
• Validate Binary Search Tree - Verifies the BST property that insertion relies on to choose the correct position
• Delete Node in a BST - The inverse of insertion, removing a node while maintaining BST structure