LeetCode 701: Insert into a Binary Search Tree

Problem Restatement

We are given the root of a binary search tree and a value val.

We need to insert val into the tree while keeping the binary search tree property valid.

A binary search tree has this rule:

The problem guarantees that val does not already exist in the tree.

Return the root of the tree after insertion.

There may be more than one valid insertion result. Any valid BST is accepted.

Input and Output

The function shape is:

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        ...

Examples

Example 1:

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

The value 5 should be inserted into the BST.

Start at 4.

Since 5 > 4, go right to 7.

Since 5 < 7, go left.

The left child of 7 is empty, so insert 5 there.

One valid output is:

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

Example 2:

root = [40, 20, 60, 10, 30, 50, 70]
val = 25

Start at 40.

25 < 40, so go left to 20.

25 > 20, so go right to 30.

25 < 30, so go left.

The left child of 30 is empty, so insert 25 there.

First Thought: Rebuild the Tree

One possible idea is to collect all values from the tree, add val, sort the values, and build a new BST.

That works, but it does much more work than needed.

We do not need to change the whole tree. A BST already tells us where the new value belongs. We only need to walk down one path from the root to an empty child position.

Problem With Rebuilding

Rebuilding visits every node.

If the tree has n nodes, this costs at least:

O(n)

It also uses extra memory to store all values.

But insertion into a BST only depends on the tree height h.

If the tree is balanced, h is about log n.

So a direct insertion can be much cheaper than rebuilding the full tree.

Key Insight

At every node, the BST property tells us exactly which direction to go.

If val is smaller than the current node value, it belongs somewhere in the left subtree.

If val is greater than the current node value, it belongs somewhere in the right subtree.

We continue until we find an empty child position.

That empty position is a valid place to insert the new node.

Algorithm

Use recursive traversal.

At each node:

1. If the current node is None, create and return a new node with val.
2. If val < root.val, insert val into the left subtree.
3. If val > root.val, insert val into the right subtree.
4. Return root.

The recursive return is important.

When insertion happens under a child pointer, the call returns the modified subtree root. We assign it back to root.left or root.right.

Correctness

We prove that the algorithm returns a valid BST containing all original nodes plus val.

If root is None, the algorithm creates a single node containing val. A single-node tree is a valid BST.

Now assume root is not None.

If val < root.val, the value must be inserted into the left subtree to preserve the BST ordering. The algorithm recursively inserts it there. By the recursive assumption, the left subtree remains a valid BST and contains val. Since val is smaller than root.val, and every node in the left subtree is still on the left side of root, the full tree remains valid.

If val > root.val, the same reasoning applies to the right subtree. The inserted value belongs on the right side of root, and the recursive call preserves the right subtree as a valid BST.

The algorithm never moves or changes existing node values. It only attaches one new node at an empty position reached by valid BST comparisons. Therefore the returned tree contains all original nodes, contains val, and satisfies the BST property.

Complexity

Let h be the height of the tree.

If the tree is balanced, h = O(log n).

If the tree is skewed, h = O(n).

Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None:
            return TreeNode(val)

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

        return root

Code Explanation

The base case handles an empty position:

if root is None:
    return TreeNode(val)

This is where the new value is inserted.

If the value is smaller than the current node, it must go into the left subtree:

if val < root.val:
    root.left = self.insertIntoBST(root.left, val)

If the value is larger, it must go into the right subtree:

else:
    root.right = self.insertIntoBST(root.right, val)

The problem guarantees that val does not already exist, so the else branch means val > root.val.

Finally, return the current root:

return root

This keeps the original root of the tree unchanged unless the original tree was empty.

Iterative Version

The recursive version is short and natural, but the iterative version avoids recursion stack space.

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        new_node = TreeNode(val)

        if root is None:
            return new_node

        cur = root

        while True:
            if val < cur.val:
                if cur.left is None:
                    cur.left = new_node
                    break
                cur = cur.left
            else:
                if cur.right is None:
                    cur.right = new_node
                    break
                cur = cur.right

        return root

This version uses the same comparison logic.

The only difference is that it directly attaches the new node once it finds an empty child pointer.

Iterative Complexity

Testing

For local testing, we can insert values and verify the inorder traversal stays sorted.

A BST inorder traversal should produce values in increasing order.

def inorder(root):
    if root is None:
        return []

    return inorder(root.left) + [root.val] + inorder(root.right)

def test_insert_into_bst():
    s = Solution()

    root = TreeNode(4)
    root.left = TreeNode(2)
    root.right = TreeNode(7)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(3)

    root = s.insertIntoBST(root, 5)

    assert inorder(root) == [1, 2, 3, 4, 5, 7]

    root = None
    root = s.insertIntoBST(root, 10)

    assert inorder(root) == [10]

    root = TreeNode(8)
    root.left = TreeNode(4)
    root.right = TreeNode(12)

    root = s.insertIntoBST(root, 2)

    assert inorder(root) == [2, 4, 8, 12]

    print("all tests passed")

Test coverage: