BST Search and Insert

Description

A binary search tree keeps one rule at every node: smaller keys to the left, larger to the right. That rule turns search into a single walk from the root, because each comparison throws away a whole subtree. Insert is the same walk, adding a node where the search falls off. This skill makes both automatic, and shows why the tree's shape, not its size, decides how fast they are.

We'll go from simple to more technical:

1. The pattern: one compare-and-pick-a-side walk for search and insert.
2. A second flavor: iterative insert with a parent pointer.
3. Where ordered trees run in production (sorted maps, database indexes).
4. What breaks it: sorted input, duplicate keys and a dropped return value.

The approach

In a BST, comparing with one node tells you which side the value must be on. So search walks one path: left if the value is smaller, right if it's larger. Insert walks the same path, and when it falls off the tree, the new node goes exactly there.

Inserting 6 into the tree 8 / 4, 12 / 2, 7:

boolean searchBST(TreeNode root, int val) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val == val) return true;
        cur = (val < cur.val) ? cur.left : cur.right;   // the other side can't contain val
    }
    return false;
}

TreeNode insert(TreeNode node, int val) {
    if (node == null) return new TreeNode(val);       // fell off the tree - this is where val belongs
    if (val < node.val) node.left = insert(node.left, val);
    else if (val > node.val) node.right = insert(node.right, val);
    return node;                                      // an equal key is ignored: this BST is a set
}

def search_bst(root: TreeNode | None, val: int) -> bool:
    cur = root
    while cur is not None:
        if cur.val == val:
            return True
        cur = cur.left if val < cur.val else cur.right   # the other side can't contain val
    return False


def insert(node: TreeNode | None, val: int) -> TreeNode:
    if node is None:
        return TreeNode(val)                 # fell off the tree - this is where val belongs
    if val < node.val:
        node.left = insert(node.left, val)
    elif val > node.val:
        node.right = insert(node.right, val)
    return node                              # an equal key is ignored: this BST is a set

The assignment node.left = insert(...) is what links the new node to its parent on the way back up. Each step discards a whole subtree, so both operations cost O(height).

A second flavor: iterative insert

The recursive insert keeps O(height) stack frames just to relink the path on the way back. The iterative version only remembers the last node it passed, parent, and which side it fell off:

TreeNode insertIterative(TreeNode root, int val) {
    TreeNode node = new TreeNode(val);
    if (root == null) return node;                     // empty tree: the new node is the root
    TreeNode parent = null, cur = root;
    while (cur != null) {
        if (val == cur.val) return root;               // already present
        parent = cur;
        cur = (val < cur.val) ? cur.left : cur.right;
    }
    if (val < parent.val) parent.left = node; else parent.right = node;
    return root;
}

def insert_iterative(root: TreeNode | None, val: int) -> TreeNode:
    node = TreeNode(val)
    if root is None:
        return node                          # empty tree: the new node is the root
    parent, cur = None, root
    while cur is not None:
        if val == cur.val:
            return root                      # already present
        parent = cur
        cur = cur.left if val < cur.val else cur.right
    if val < parent.val:
        parent.left = node
    else:
        parent.right = node
    return root

Same O(height) time, O(1) extra space. Once cur is null, parent is the only way back to the node that needs the new child.

Where you'll see it

Java's TreeMap is a balanced BST (a red-black tree), and database indexes use B-trees, a wider relative. Both cost time in proportion to the tree's height, not its size. Python's standard library has no tree-based sorted map; the sortedcontainers package is the usual stand-in.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Keys 1, 2, 3, 4, 5 are inserted in that order into an empty BST. What shape is the tree, and what does a search cost?

2. Why write node.left = insert(node.left, val) instead of just calling insert(node.left, val)?

3. Insert sends an equal key to the right, and search stops at the first equal node. Can a duplicate be missed?

Key takeaways

• Each comparison discards a whole subtree, so search and insert walk one path: O(height).
• Insert is a search that attaches a new node where the search falls off.
• Height decides the cost. Sorted inserts build a chain; balanced trees stay O(log n).
• Pick one rule for equal keys and use it everywhere.