Binary search trees

Problem

A plain tree cannot answer "is 13 in here?" without looking at every node. A search tree can: compare with the root, go left or right, repeat. If the tree is reasonably balanced that takes about log n steps, the same as binary search on a sorted array, but the tree also supports cheap insertion and deletion, which a sorted array does not. The interview questions test whether you hold the invariant precisely. The common failure is checking only a node against its parent, when the promise is about every ancestor.

Intuition

Picture a library whose shelves are arranged so that, at every shelf, books to your left come earlier in the alphabet and books to your right come later. To find a title you never scan; you ask at each shelf "left or right?" and walk away from the wrong half. That works because the rule holds for the whole half, not just the next shelf over. If one shelf deep on the right there is a book that belongs far to the left, the search will walk right past it and conclude it is missing.

This is why the invariant is stated for subtrees, and why validation passes a range down. Each time you step left, the node's value becomes the new upper limit; each time you step right, it becomes the new lower limit. The range only ever shrinks, and every node must lie strictly inside the range it inherits. The inorder walk is the same fact told as a list: reading left subtree, node, right subtree gives a strictly increasing sequence exactly when the promise holds everywhere, by induction on the subtree.

Every node sits at its sorted position from left to right, so reading the bottom edge of the picture gives the inorder list. The amber path is how you find the common ancestor of 4 and 7: go left of 8 (both are smaller), go right of 3 (both are larger), and stop at 6, where they split.

Mechanics

The invariant, stated carefully

For every node x: all values in x's left subtree are less than x.val, and all values in x's right subtree are greater. Whether duplicates are allowed, and on which side, changes by problem; the strict version used here has none. The local test "left child < node < right child" is necessary but not sufficient: it misses a value that is correct against its parent but wrong against a grandparent.

Validating with intervals

Walk the tree carrying (low, high), starting at (-inf, +inf). A node is acceptable if low < val < high. Its left child inherits (low, val) and its right child (val, high). If every node passes, every ancestor-descendant pair has been checked, because each ancestor contributed a bound to every node below it. The alternative, checking that the inorder sequence is strictly increasing by remembering the previous value, is equivalent and often shorter.

Searching, inserting and the descent loop

Find, insert and the common ancestor all share one loop: compare, then go to one child. Insertion walks until it falls off the tree and attaches the new node where the search ended, which is the only place the invariant allows it. None of these need recursion; a while loop uses O(1) extra space. The cost is the height, which is log n for a balanced tree and n for a tree built from already-sorted input, since every insert then goes right.

Deleting a node

Find the node, then handle three cases. A leaf is simply removed. A node with one child is replaced by that child. A node with two children cannot be replaced by either child without breaking something, so copy the value of its inorder successor (the smallest value in the right subtree: go right once, then left as far as possible) into it, and delete the successor from the right subtree, where it has at most one child. The successor is the only value that is larger than everything on the left and no larger than everything else on the right, which is why swapping it in keeps the invariant.

Allowed interval under each node. The walk stops at the amber node, so the nodes after it get no interval. Locally, 3 < 6 < 7 looks fine; globally, 3 is on the right of 5 and must be larger than 5.

Worked example

Validation. The tree in the second diagram, walked in preorder with the inherited interval:

Node 3 fails its interval (5, 6), so the whole tree is rejected after 4 steps without looking at the rest.

k-th smallest and common ancestor. On the valid tree in the first diagram, the inorder list is 1, 3, 4, 6, 7, 8, 10, 13, 14. Asking for the 4th smallest value, the walk visits 1, 3, 4, 6 and stops. The 4th smallest value is 6, and nothing to the right of it was touched. For the common ancestor of 4 and 7, the descent visits 8, 3, 6: at 8 both are smaller so go left, at 3 both are larger so go right, and at 6 one is on each side or equal, so the lowest common ancestor is 6.

Deleting. Removing the leaf 13 leaves inorder 1, 3, 4, 6, 7, 8, 10, 14. Removing 3, which has two children, copies in its successor 4 (the leftmost value of the right subtree) and deletes the old 4 below it: the root's left child is now 4 and the inorder list is 1, 4, 6, 7, 8, 10, 13, 14, still sorted.

Implementation

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


def is_valid_bst(root):
    def ok(node, low, high):
        if not node:
            return True
        if not (low < node.val < high):
            return False
        return ok(node.left, low, node.val) and ok(node.right, node.val, high)

    return ok(root, float("-inf"), float("inf"))


def kth_smallest(root, k):
    stack, cur = [], root
    while stack or cur:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        k -= 1
        if k == 0:
            return cur.val
        cur = cur.right


def lca_bst(root, p, q):
    node = root
    while node:
        if p.val < node.val and q.val < node.val:
            node = node.left
        elif p.val > node.val and q.val > node.val:
            node = node.right
        else:
            return node


def insert(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root


def search(root, val):
    while root and root.val != val:
        root = root.left if val < root.val else root.right
    return root


def delete(root, key):
    if not root:
        return None
    if key < root.val:
        root.left = delete(root.left, key)
    elif key > root.val:
        root.right = delete(root.right, key)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        succ = root.right
        while succ.left:
            succ = succ.left
        root.val = succ.val
        root.right = delete(root.right, succ.val)
    return root


def inorder_successor(root, p):
    succ = None
    while root:
        if p.val < root.val:
            succ = root                              # last node where we turned left
            root = root.left
        else:
            root = root.right
    return succ


def sorted_array_to_bst(nums):
    if not nums:
        return None
    mid = len(nums) // 2
    return TreeNode(nums[mid], sorted_array_to_bst(nums[:mid]), sorted_array_to_bst(nums[mid + 1:]))

is_valid_bst uses infinities so the first comparison needs no special case; if node values can be as extreme as the integer limits, use None bounds instead of sentinels. kth_smallest is the iterative inorder from the previous page with an early return. sorted_array_to_bst copies slices for clarity, which costs O(n log n); pass index bounds to make it O(n).

Variations and edge cases

• Previous-value validation. Do an inorder walk and keep the previous value; the tree is valid when each value is greater than the one before. It needs one variable but must compare against the previous visited value, not the parent.
• Augmented trees. To answer many k-th smallest queries, store each node's subtree size and descend: if the left size is at least k go left, if it equals k-1 stop here, otherwise go right with k reduced. That gives O(h) per query.
• Recover a swapped pair. Inorder walk, record the places where a value is smaller than its predecessor; the first descent's larger value and the last descent's smaller value are the swapped nodes.
• Balancing. Interview BSTs are usually unbalanced and their cost is O(h). Self-balancing trees (red-black, AVL) keep h at O(log n); you describe them rather than implement them.
• Edge cases: an empty tree (valid), a single node, duplicates (confirm the rule and make the comparison strict or non-strict on one side only), a skewed tree of 10⁵ nodes that exceeds the recursion limit, deleting the root, and deleting a key that is absent.

Complexity and tradeoffs

• Time: search, insert, delete and common ancestor take O(h). Validation visits every node: O(n). The k-th smallest takes O(h + k) because the walk goes down the left spine first. In the example, the 4th smallest of 9 values needed 4 visits plus the spine.
• Space: O(h) for a stack or recursion, O(1) for the descent loops that need none.
• Baseline. Searching an unordered tree is O(n); searching a sorted array is O(log n) but insert and delete are O(n) because elements shift. A balanced search tree gives O(log n) for all three.
• When it fails. An unbalanced tree degrades every O(h) bound to O(n). Heavy repeated insertions of sorted data are the classic cause. Also, a search tree orders by one key; for "k-th smallest" under many updates, a balanced tree with subtree sizes or a Fenwick tree is the better fit.

Problems

The home problems use the invariant in four ways: checking it (validate), reading it in order (k-th smallest, inorder successor), descending by it (lowest common ancestor, insert) and repairing it (delete). Converting a sorted array into a balanced tree builds a tree and lives with tree construction; it appears below.

Medium

• 98. Validate Binary Search Tree Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Pass down the open interval each node must fall inside, tightening the upper bound going left and the lower bound going right.
• 230. Kth Smallest Element in a BST Blind 75 Grind 169 NeetCode 150 NeetCode 250
  An inorder traversal visits a BST in sorted order, so stop at the kth node visited.
• 235. Lowest Common Ancestor of a Binary Search Tree Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Walk down from the root: if both values are smaller go left, if both are larger go right, otherwise this node is where they split.
• 285. Inorder Successor in BST Grind 169
  Walk down from the root, and every time you go left remember that node, since it is the smallest value seen so far that is larger than the target.
• 450. Delete Node in a BST NeetCode 250
  To delete a node with two children, replace its value with its inorder successor's and delete that successor from the right subtree.
• 701. Insert into a Binary Search Tree NeetCode 250
  Walk down the BST comparing values until you reach an empty child, and attach the new node there.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 108. Convert Sorted Array to Binary Search Tree Easy

Connections

This page is the tree version of binary search: the same "discard half" argument, with pointers instead of indices. It reuses the traversals from the depth-first page, especially inorder. The iterator and successor ideas return in heap and ordered-structure problems, and the sorted-array-to-tree construction appears again when you build trees from traversals.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 12 (binary search trees: querying, successor and predecessor, insertion and deletion) and chapter 13 (red-black trees).
• Sedgewick and Wayne, Algorithms, section 3.2: binary search trees, with rank and select via subtree sizes.
• Skiena, The Algorithm Design Manual, the dictionary data structures chapter: binary search trees and their balance.
• Adelson-Velsky and Landis, "An algorithm for the organization of information" (1962), the original self-balancing search tree.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.