BSTBinary search trees

01Why it exists

Reach for it when you see:Ordered sets, range queries, predecessor and successor, the k-th smallest, needing inserts and lookups together, in-order gives sorted output.

02The core idea

A binary search tree adds exactly one rule: for every node, every value in the left subtree is smaller than it and every value in the right subtree is larger. Note that it is the whole subtree, not just the immediate children. That rule lets every comparison throw away an entire subtree: if the target is smaller you only look left, if it is larger you only look right, which is the same idea as binary search.

Search compares its way down from the root. Insert is a search that runs off the end and hangs the new node in the empty spot, which is why a new node is always a leaf. Delete splits into three cases: a node with no children is simply removed; with one child, the child moves up; with two children it cannot be removed directly, so find the in-order successor (the leftmost node of the right subtree, which by definition has no left child), copy its value up, and then delete the successor from the right subtree. Left < node < right still holds afterwards.

Every operation costs the height h. Inserting in random order keeps h around log n, but inserting already-sorted data in order degenerates the tree into a chain with h = n, and the BST becomes a linked list. That is exactly the problem the next lesson on balanced trees solves.

An in-order traversal is the sorted order, and that is the property BST problems lean on most. The k-th smallest is the k-th node in order; a BST can be validated by checking that the in-order sequence is strictly increasing; a range query is an in-order traversal pruned by "stop going that way once you are outside the range".

03The algorithm

1. 1Search and insert: start at the root and go left when the target is smaller than the node, right when it is larger. A search returns on equality and reports absence when it reaches an empty spot; an insert puts the new node in that empty spot.
2. 2Delete: find the node first. With 0 or 1 child, replace it with that child (or with nothing).
3. 3With 2 children: walk into the right subtree and keep going left to reach the successor, copy the successor's value into this node, then recursively delete the successor from the right subtree (it has at most a right child, so it falls into the previous case).
4. 4Validation: recurse downward carrying a (lo, hi) range, replacing hi with the node's own key on the way left and lo on the way right. Every node must fall strictly inside its range.
5. 5Range query and k-th smallest: use an in-order traversal, pruned by "once the value is below lo do not go left, once it is above hi do not go right", or stop as soon as the count reaches k.

04Interactive demo

Seven values are inserted in turn to build the tree, then one key that exists and one that does not are searched for, then 45 is inserted, and finally 30 — a node with two children — is deleted, so you can watch the successor 40 move up into its place.

05Code

The three basic operations, search, insert and delete, plus the two things interviewers ask for most: validation and range queries. Writing delete recursively as "return the new root of this subtree" means the parent never needs a special case.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


def search(node, key):
    """Every comparison throws away a whole subtree. O(h)"""
    while node and node.key != key:
        node = node.left if key < node.key else node.right
    return node


def insert(node, key):
    """Recursive version: returns the root of this subtree after the insertion"""
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    return node                       # an equal key is not inserted twice


def delete(node, key):
    if node is None:
        return None
    if key < node.key:
        node.left = delete(node.left, key)
    elif key > node.key:
        node.right = delete(node.right, key)
    else:
        # found it, and there are three cases
        if node.left is None:         # 0 or 1 child: splice in the other side
            return node.right
        if node.right is None:
            return node.left
        succ = node.right             # 2 children: take the smallest key on the right (the in-order successor)
        while succ.left:
            succ = succ.left
        node.key = succ.key           # overwrite this node's key with the successor's
        node.right = delete(node.right, succ.key)   # then delete the successor from the right subtree
    return node


def is_valid_bst(node, lo=float("-inf"), hi=float("inf")):
    """Validation: every node must sit inside the bounds its ancestors set. Comparing with the parent is not enough."""
    if node is None:
        return True
    if not (lo < node.key < hi):
        return False
    return is_valid_bst(node.left, lo, node.key) and is_valid_bst(node.right, node.key, hi)


def range_query(node, lo, hi, out):
    """List every key in [lo, hi]: an in-order traversal with pruning"""
    if node is None:
        return
    if lo < node.key:
        range_query(node.left, lo, hi, out)
    if lo <= node.key <= hi:
        out.append(node.key)
    if node.key < hi:
        range_query(node.right, lo, hi, out)

06Practice

• LeetCode 700Search in a Binary Search TreeEasy
• LeetCode 701Insert into a Binary Search TreeMedium
• LeetCode 450Delete Node in a BSTMedium
• LeetCode 98Validate Binary Search TreeMedium
• LeetCode 230Kth Smallest Element in a BSTMedium
• LeetCode 235Lowest Common Ancestor of a BSTMedium
• LeetCode 108Convert Sorted Array to BST (build a balanced one)Easy