BST Operations · bigonotes

In a binary search tree (BST) every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger. That ordering lets you prune: each comparison discards one whole side. So search, insert and delete follow a single path and cost $O(h)$ , where $h$ is the height. The one idiom worth mastering is re-attach on return: every call returns the (possibly new) root of its subtree, and the parent stores it.

The idea#

Search is a walk: smaller goes left, larger goes right, equal means found.

Insert and delete change the shape. The clean way to handle that is to let each call return the root of its subtree and have the parent write it back: node.left = insert(node.left, val). When the recursion reaches an empty spot, it returns the new node, and the parent links it in. When a node is deleted, the call returns whatever should take its place, and again the parent links it in. Nobody has to remember "who is my parent".

Delete is the hard one, because removing a node leaves a gap that something must fill. It has three cases:

Node to delete	What to do
A leaf	Return `None`. This matters: it is how the parent learns the child is gone.
Has a right child	Copy in the successor (smallest value in the right subtree), then delete that value from the right subtree.
Has only a left child	Copy in the predecessor (largest value in the left subtree), then delete that value from the left subtree.

Copying the successor keeps the ordering. It is larger than everything on the left and smaller than everything else on the right.

How to spot it#

The input is a BST and the task uses its ordering.

"Search", "insert", "delete", "floor", "ceiling" in a BST.
"Validate" a BST, or "k-th smallest": these use the ordering through an inorder walk or a range.
Two values in a BST and their common ancestor: the values split at the answer.

Template#

Here is the re-attach-on-return idea as one shape that covers both insert and delete. Every call returns the root of the subtree it was given. Nodes follow LeetCode's TreeNode(val, left, right).

change(node, key):
    if node is None:
        return what belongs in the empty spot   # new node, or None
    if key > node.val:
        node.right = change(node.right, key)    # re-attach the right side
    elif key < node.val:
        node.left = change(node.left, key)      # re-attach the left side
    else:
        handle this node; return its replacement
    return node                                 # the parent keeps us

Insert without return values#

You will also see insert written without return values: walk down until the child you need is missing, then attach the new node there. It works, but you must handle an empty tree separately, and the code has two near-identical branches. The return-the-node style handles every case in one shape, and it is the same shape delete needs.

Pitfalls#

These mistakes lose subtrees or break the ordering.

Not returning the node. If a call doesn't return its subtree's root, the parent writes None over a real subtree.
A leaf that doesn't report. Setting a local variable to None changes nothing for the parent; you must return None.
Deleting the copied value from the wrong side. After copying the successor, delete it from the right subtree. After copying the predecessor, delete it from the left.
Checking only parent and child. A BST rule covers whole subtrees, not just the direct children.
Assuming $O(\log n)$ . Operations are $O(h)$ . A BST built from sorted input is a linked list, with $h = n$ .

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Search in a Binary Search Tree

A loop is enough. Go left when the target is smaller, right when it is larger, and stop when you find it or reach None.

Hint: Insert into a Binary Search Tree

Use the template. The empty spot returns TreeNode(val), and each parent re-attaches the child it recursed into.

Hint: Delete Node in a BST

Follow the three cases in the table. For the successor, step right once, then walk left until there is no left child. Copy its value in, then call delete for that value on the right subtree and re-attach the result.

Hint: Validate Binary Search Tree

Comparing each node with its children is not enough. Pass down the range a node may sit in: start at (-inf, +inf), narrow to (lo, node.val) on the left and (node.val, hi) on the right. An inorder walk that stays strictly increasing also works. See Top-Down State and Path Prefix Sums.

Hint: Kth Smallest Element in a BST

An inorder walk visits values in sorted order. Count visits and stop at the k-th. See Pick the Traversal.

Hint: Lowest Common Ancestor of a Binary Search Tree

Walk down from the root. If both values are smaller than the node, go left; if both are larger, go right. The first node where they split is the answer.

Key takeaways#

Each comparison discards one side, so BST operations cost $O(h)$ .
Return the subtree root from every call and let the parent re-attach it.
Delete: a leaf returns None; otherwise copy the successor (or predecessor) and delete it below.
A valid BST needs a range check, not just a parent-child check.

Core idea#

In a BST, every value in the left subtree is smaller and every value in the right subtree is larger. Each comparison discards one side, so search, insert and delete cost $O(h)$ . Every call returns the root of its subtree, and the parent re-attaches it.

Key points#

Search: smaller goes left, larger goes right, equal means found.
Insert: node.left = insert(node.left, val). An empty spot returns the new node.
Re-attach on return means no call needs to know its parent.
Validate: pass down an allowed range, from (-inf, inf) to (lo, node.val) and (node.val, hi). An inorder walk of a valid BST is strictly increasing.
K-th smallest: inorder visits values in sorted order. Stop at visit k.
LCA of two values: the values split at the answer.

Delete cases#

Node to delete	Action
Leaf	return `None`
Has a right child	copy the successor (min of right), delete it from the right
Only a left child	copy the predecessor (max of left), delete it from the left

Template#

delete(node, key):
    if node is None: return None
    if key > node.val: node.right = delete(node.right, key)
    elif key < node.val: node.left = delete(node.left, key)
    elif node is a leaf: return None          # tell the parent
    elif node.right exists:
        succ = smallest node in the right subtree
        node.val = succ.val
        node.right = delete(node.right, succ.val)
    else:                                     # mirror: predecessor
        pred = largest node in the left subtree
        node.val = pred.val
        node.left = delete(node.left, pred.val)
    return node                               # parent re-attaches

Pitfalls#

Not returning the node. The parent writes None over a real subtree.
A leaf that sets a local to None. It must return None.
Deleting the copied value from the wrong side.
Assuming $O(\log n)$ . Sorted input builds a linked list, so $h = n$ .

Say it in an interview#

"Each call returns its subtree root, and the parent re-attaches it."
"BST operations are O(h), which is O(n) on a skewed tree."