Binary Trees and BSTs

1. What It Is and Why It Exists

A binary tree is a hierarchy where each node has at most two children (left, right). It exists to model anything naturally branching or recursive — parse trees, decision trees, file systems — and because the recursive shape makes "solve the whole tree = combine solutions of the two subtrees" the default solution strategy. Most binary-tree interview problems are one recursive function over (left subtree, right subtree).

A binary search tree (BST) adds one invariant: for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger. That ordering is what makes a BST useful: search/insert/delete each follow a single root-to-leaf path, so they cost O(h) where h is the height. The "why it works" intuition: a BST is binary search made dynamic — each comparison discards one subtree, so on a balanced tree h = O(log n) and operations are O(log n). The catch interviewers always probe: inserting sorted data degenerates the BST into a linked list, h = n, and everything becomes O(n) — which is why self-balancing trees exist.

2. Operations and Complexity

Here n is the number of nodes and h the longest root-to-leaf path length. In-order visits left subtree, node, right subtree; pre-order visits node first; post-order visits node last; level-order visits one depth at a time. We assume distinct keys, so the BST inequalities are strict.

Space: O(n) for the tree; recursive depth-first traversal uses an O(h) call stack (O(log n) balanced, O(n) skewed). During level-order traversal, the queue can contain unprocessed nodes from the current level and children already added from the next, using O(n) space in the worst case. Storing all traversal results also takes O(n). Guided search, insertion, deletion, and min/max lookup cost O(h), which is O(log n) only if balanced; a full traversal still costs O(n). In-order traversal of a BST produces sorted keys, the property used in validation, kth-smallest, and iterator problems.

3. Implementation

The implementation shows search, insertion, deletion, in-order traversal, and level-order traversal. Insert only keys not already present: the insertion routine does not reject duplicates, while this tutorial assumes a strict BST. bst_search returns the matching node or None; assign the return value of insertion/deletion back to the root because it may change.

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

def bst_search(root, key):               # O(h): each step discards one subtree
    while root and root.val != key:
        root = root.left if key < root.val else root.right
    return root

def bst_insert(root, key):               # O(h)
    if root is None:
        return TreeNode(key)
    if key < root.val:
        root.left = bst_insert(root.left, key)
    else:
        root.right = bst_insert(root.right, key)
    return root

def bst_delete(root, key):               # O(h)
    if root is None:
        return None
    if key < root.val:
        root.left = bst_delete(root.left, key)
    elif key > root.val:
        root.right = bst_delete(root.right, key)
    else:                                # found it
        if not root.left:  return root.right    # 0/1 child
        if not root.right: return root.left
        succ = root.right                # 2 children: in-order successor
        while succ.left:
            succ = succ.left
        root.val = succ.val
        root.right = bst_delete(root.right, succ.val)
    return root

def inorder(root, out):                  # BST in-order => SORTED keys
    if root:
        inorder(root.left, out)
        out.append(root.val)
        inorder(root.right, out)

# Level-order (BFS) needs a queue, not recursion:
from collections import deque
def level_order(root):
    res, q = [], deque([root] if root else [])
    while q:
        level = []
        for _ in range(len(q)):          # snapshot size = one full level
            n = q.popleft()
            level.append(n.val)
            if n.left:  q.append(n.left)
            if n.right: q.append(n.right)
        res.append(level)
    return res

There is no idiomatic stdlib BST in Python — implement TreeNode yourself (interview problems hand you one). For an ordered collection, a third-party option is sortedcontainers.SortedList/SortedDict if dependencies are allowed. Its implementation and complexity guarantees differ from a balanced BST; the bounds above describe the node-based tree.

4. When to Reach for It

• Input is given as a tree (TreeNode root) — traversal, depth, path, lowest common ancestor (LCA), validation, and serialization problems. The LCA is the deepest node that is an ancestor of both targets, allowing a node to be its own ancestor.
• The phrase "in-order / sorted order" appears with a BST → in-order traversal yields sorted keys (kth-smallest, validate-BST, BST iterator).
• You need a dynamic ordered set supporting insert/delete and min/max/predecessor/successor/range — a balanced BST (or SortedList); a hash table can't do ordering.
• Recursive "combine left and right subtree answers" structure (height, diameter, path sums, tree DP).
• BFS keyword "level" → level-order traversal with a queue.

5. Common Pitfalls

• Assuming O(log n): BST ops are O(h); a skewed tree (sorted inserts) makes them O(n). Always state "O(h), O(log n) if balanced".
• Validating a BST by checking only direct children: the property is global. Pass down (low, high) bounds, or check that the in-order traversal is strictly increasing.
• BST delete with two children done wrong: must replace with the in-order successor (smallest in right subtree) or predecessor, then delete that node — not just splice.
• Recursion depth: O(h) stack; a deep/skewed tree can hit Python's recursion limit — mention an explicit stack as the iterative alternative.
• Empty tree / single node: every traversal and recursion must handle root is None as the base case.
• Confusing tree shapes: complete means every level is full except possibly the last, filled from the left; full means every node has zero or two children; perfect means full with all leaves at the same depth. Balanced concerns subtree heights and keeps height O(log n); a full tree need not be balanced.

6. Interview Cheat Sheet

• "BST search/insert/delete are O(h) — O(log n) if balanced, O(n) if skewed by sorted inserts."
• "In-order traversal of a BST yields keys in sorted order — that's how I validate a BST or get the kth smallest."
• "Most binary-tree problems are one recursion: solve left, solve right, combine — base case root is None."
• "Level-order uses a queue with a per-level size snapshot; the other three traversals are recursion (or an explicit stack to avoid depth limits)."

Follow-ups:

• "How do you keep a BST balanced?" — Self-balancing variants (AVL, red-black) rotate on insert/delete to keep h = O(log n); in Python interviews you'd cite sortedcontainers rather than code a red-black tree.
• "Validate a BST." — Recurse with (low, high) bounds, tightening them as you descend; or assert the in-order traversal is strictly increasing. O(n).
• "Lowest common ancestor in a BST?" — Walk from the root: both targets smaller → go left, both larger → go right, otherwise this node is the split point and the LCA. O(h).