Binary Search Trees

Every operation on a binary search tree - search, insert, delete - is the same walk: compare the target against the current node, go left or right, repeat. That one walk is the whole idea. Everything else on this page is either a consequence of it or a trap in implementing it.

1. The invariant

A binary search tree orders every node so that, for every node v:

every value in v's left subtree is less than v.val, and
every value in v's right subtree is greater than v.val.

The word doing the work there is subtree, not children. The invariant is about the whole subtree, at every depth, not just the node directly below.

Comparing only against the parent misses the range

node.left.val < node.val and node.right.val > node.val, checked at every node, is not sufficient. It only ever compares a node to its direct parent, never to an ancestor two or more levels up. The counterexample above passes that check at every single node and is still invalid. The fix - carrying a (lo, hi) range down the recursion - is section 6.

Try it yourself: insert, search, and watch the descent one comparison at a time. The "Sorted inserts" preset builds the exact same seven values in a different order and the tree that comes out barely looks related.

Fig. BST Explorer

The tree

Operate

while node:
    if target == node.val: return node
    node = node.left if target < node.val \
           else node.right

Inorder walk

20304050607080

n = 7 · height = 2 · worst-case comparisons = 3
Insert or find a value and watch the descent. One comparison per level, and the level count is the cost.

2. Search: one comparison per level

Search is the walk with nothing else attached: compare, and step left or right until you find the value or fall off the tree.

def search(root, target):
    node = root
    while node:
        if target == node.val:
            return node
        node = node.left if target < node.val else node.right
    return None

Searching for 60 costs exactly 2 comparisons: 50 sends you right, 70 sends you left, and 60 is found on the third look. The cost is the DEPTH of the answer, not the size of the tree.

Every step throws away one entire subtree without looking at it. That is the whole reason the cost is bounded by the tree's height, not its node count: on a tree of n nodes shaped as close to a straight line as possible, height is n; shaped as close to complete as possible, height is log2 n.

	Balanced tree	Degenerate tree
Height	`O(log n)`	`O(n)`
Search / insert / delete	`O(log n)`	`O(n)`
Worst case happens when	insertions arrive in a roughly random or pre-balanced order	insertions arrive already sorted (or reverse-sorted)
Fixed by	nothing - a plain BST does not rebalance itself	a self-balancing variant; see Keeping a Tree Balanced

3. Insert

Insertion runs the exact same descent as search, and stops the first time it would fall off the tree - which is exactly the None that search returns on a miss. The new node is hung there.

def insert(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    return root                       # val == root.val: no duplicates, no-op

45 compares less than 50, less than 40's... no - greater than 40, so it falls off the tree at 40's empty right child, and that is where it is hung. Nothing above it moves.

Insertion never restructures a plain BST - it only ever adds a leaf.

The descent is exactly the search for the value that is not there yet, and the new node is hung off whichever null child the search bottomed out at. This is also why repeated insertion has no self-correcting effect on shape: nothing about a leaf-only insert can turn a bad shape into a better one, which is the setup for section 8.

4. Delete: the three cases

Deletion is the one operation that is not just "the descent, then stop." Once you find the node, what you do with it depends on how many children it has.

Case	What to do
Leaf (no children)	Detach it. Its parent simply points to `None` instead.
One child	Splice the child into the node's own place - the parent now points directly at the child, skipping the deleted node.
Two children	Do not delete the node itself. Copy in its inorder successor's value (the smallest value in the right subtree), then delete that successor instead - which is now guaranteed to be a leaf or a one-child case.

def delete(root, val):
    if root is None:
        return None
    if val < root.val:
        root.left = delete(root.left, val)
    elif val > root.val:
        root.right = delete(root.right, val)
    else:
        if root.left is None:
            return root.right          # handles leaf AND one-right-child
        if root.right is None:
            return root.left           # one-left-child
        succ = root.right
        while succ.left:               # smallest value in the right subtree
            succ = succ.left
        root.val = succ.val
        root.right = delete(root.right, succ.val)
    return root

The leaf case is not a separate branch

A leaf does not need its own if - it falls out of the one-child cases for free. A leaf has root.left is None AND root.right is None, so if root.left is None: return root.right already returns None for a leaf. Writing an explicit leaf branch first is not wrong, just redundant; the three-case table above is about reasoning, the code only needs two ifs.

Copying in the predecessor (largest value in the left subtree) instead of the successor is equally correct - the invariant only requires some value that sits between the deleted node's neighbours in sorted order, and both qualify. Pick one convention and use it consistently; alternating between the two in the same tree is still correct but makes deletions harder to trace by hand.

5. Inorder gives you sorted order

Walk left subtree, visit node, walk right subtree - the traversal from Traversal - and a BST hands you every value in sorted order for free.

Inorder-sorted is not a coincidence of this one example - it is the invariant, restated.

"Everything in the left subtree is smaller" plus "everything in the right subtree is bigger" plus "visit left, then self, then right" is a direct proof by induction that the walk is non-decreasing. This is also why LeetCode "Kth Smallest Element in a BST" is an inorder walk that stops after k visits rather than a sort.

6. Validating a BST

Two correct approaches, and one tempting approach that section 1 already ruled out.

Range-passing. Carry the legal (lo, hi) window down the recursion. The root's window is unbounded; a left child tightens hi to the parent's value, a right child tightens lo.

def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
    if root is None:
        return True
    if not (lo < root.val < hi):
        return False
    return (is_valid_bst(root.left, lo, root.val)
            and is_valid_bst(root.right, root.val, hi))

Inorder-and-compare. Walk the tree inorder and check the sequence is strictly increasing - a direct use of section 5's identity.

def is_valid_bst(root):
    prev = float('-inf')
    def walk(node):
        nonlocal prev
        if node is None:
            return True
        if not walk(node.left):
            return False
        if node.val <= prev:
            return False
        prev = node.val
        return walk(node.right)
    return walk(root)

Approach	What it needs	Catches duplicates?
Range-passing	two extra arguments threaded through the recursion	yes - `lo < val < hi` is strict on both ends
Inorder-and-compare	one `prev` value carried across calls (closure or class field)	yes, the same way - `node.val <= prev` rejects a repeat
`node.left.val < node.val < node.right.val` at every node	nothing extra	no help - this is the check from section 1 that misses far ancestors

Duplicate values need a decision, not just a rule

"Are equal values allowed, and on which side do they go?" is a question the problem has to answer, not one you get to assume. Most interview BSTs disallow duplicates outright, which is why the templates above use strict < and >. A tree that does allow duplicates has to pick a side for ties (conventionally the right subtree) and every one of insert, delete, search and validate has to agree on that choice, or the invariant silently breaks.

7. Successor, predecessor, and rank

The inorder successor of a node is the next value in sorted order; the predecessor is the previous one. Both split into two cases depending on whether the node has the relevant child.

	Successor (next larger)	Predecessor (next smaller)
Node has the subtree	go right once, then left as far as possible	go left once, then right as far as possible
Node doesn't have it, with parent pointers	climb until you move up from a LEFT child - that parent is the answer	climb until you move up from a RIGHT child - that parent is the answer
Node doesn't have it, no parent pointers	walk down from the root, remembering the last node you turned left away from	walk down from the root, remembering the last node you turned right away from

30 has a right subtree, so its successor is the leftmost node there: 40. 40 has no right child, so its successor is found by climbing: 40 is a right child of 30, keep climbing; 30 is a left child of 50, stop - successor is 50.

def successor_with_right_subtree(node):
    node = node.right
    while node.left:
        node = node.left
    return node
 
def successor_by_climbing(node):        # node.parent must exist
    while node.parent and node is node.parent.right:
        node = node.parent
    return node.parent                   # None if node was the maximum

Rank - "how many values in the tree are less than x" - is the same descent again, augmented: if every node also stores the size of its own subtree, a single O(h) walk answers rank without visiting every node, because at each step you either add the whole left subtree's size (you are going right, so every one of those values is less) or you don't (you are going left, so none of them count yet).

No parent pointers means no shortcut

Without a .parent field, "walk up" is not available - you have to walk down from the root and remember the last turn. Plain BST problems (as opposed to ones that explicitly say "with parent pointers") give you .left and .right only, so the successor-by-climbing code above is not usable as-is; use the root-down variant that tracks the last node you turned away from instead.

8. When the BST degenerates

Nothing about search, insert, or delete stops the tree from turning into a straight line. Insert 10, 20, 30, 40 in that order and every one of them goes to the right of the last, because every one of them is the current maximum.

Four values, inserted already sorted, and the BST that comes out has height 3 - a linked list that happens to use TreeNode instead of a next pointer.

Every guarantee from sections 2-7 was stated in terms of height, and a plain BST's height is only O(log n) if you got lucky with the insertion order. A BST built from data that is already sorted, nearly sorted, or adversarially chosen (an interviewer who inserts 1..n in order is not being subtle) is O(n) on every operation - no better than a linked list, and worse in constant factor. Fixing that without changing the search-insert-delete contract is the whole subject of the next page.

Where to go next

Keeping a Tree Balanced - rotations, AVL, red-black trees, and why a database index is neither.
Traversal and Recursion - the inorder walk this page leans on, plus the general recursion shape that search, insert, and delete are all instances of.
Practice: Binary Search Tree problems.

1. The invariant​

2. Search: one comparison per level​

3. Insert​

4. Delete: the three cases​

5. Inorder gives you sorted order​

6. Validating a BST​

7. Successor, predecessor, and rank​

8. When the BST degenerates​

Where to go next​