Trees & Binary Search Trees

Before working with trees algorithmically, you need precise shared vocabulary. A tree is a connected, acyclic undirected graph, or equivalently (for rooted trees, which are what we almost always mean in CS), a set of nodes organized in a parent-child hierarchy.

Key terms:

• Node: a single element in the tree, containing data and references to children.
• Root: the unique top-level node with no parent. Every tree has exactly one root.
• Edge: a link between a parent and a child node.
• Parent / Child: if node A has a reference to node B, A is B's parent and B is A's child.
• Leaf (or external node): a node with no children.
• Internal node: a node with at least one child.
• Subtree: a node together with all its descendants. Every node is the root of a subtree.
• Depth of a node: the number of edges from the root to that node. The root has depth 0.
• Height of a node: the number of edges on the longest path from that node down to a leaf. A leaf has height 0.
• Height of a tree: the height of its root (= the maximum depth of any node).
• Level: all nodes at the same depth form a level. The root is at level 0.
• Degree of a node: the number of its children.
• Path: a sequence of nodes where each consecutive pair is connected by an edge.
• Ancestor / Descendant: A is an ancestor of B if A is on the path from the root to B. B is then a descendant of A.
• Sibling: nodes with the same parent.

Structural properties worth knowing: A tree with n nodes has exactly n-1 edges (provable by induction: adding a node requires exactly one new edge to connect it). A binary tree is one where every node has at most 2 children, conventionally called left and right. A full binary tree has every node with exactly 0 or 2 children. A complete binary tree has all levels fully filled except possibly the last, which is filled from left to right. A perfect binary tree has all leaves at the same depth and all internal nodes have degree 2 — a perfect binary tree of height h has exactly 2^(h+1) - 1 nodes.

# Python dataclass for a binary tree node
from dataclasses import dataclass, field
from typing import Optional

@dataclass
class Node:
    val: int
    left: Optional['Node'] = field(default=None, repr=False)
    right: Optional['Node'] = field(default=None, repr=False)

def height(node: Optional[Node]) -> int:
    """Height of a node: -1 for None (empty), 0 for leaf."""
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))

def depth(root: Optional[Node], target: int, d: int = 0) -> int:
    """Depth of the node with value `target` from root."""
    if root is None:
        return -1  # not found
    if root.val == target:
        return d
    left = depth(root.left, target, d + 1)
    return left if left != -1 else depth(root.right, target, d + 1)

A traversal visits every node in a tree exactly once. For binary trees there are four canonical orderings: in-order, pre-order, post-order (all depth-first), and level-order (breadth-first). Understanding which one to use — and why — is as important as knowing how they work.

In-order (Left → Root → Right): Visit the left subtree recursively, then the current node, then the right subtree. For a BST, in-order traversal visits nodes in sorted ascending order — this is one of the most important properties in the module. Use in-order when you want sorted output.

Pre-order (Root → Left → Right): Visit the current node first, then recurse into children. Pre-order naturally serializes a tree: if you write nodes down as you visit them, you capture structure in a way that can reconstruct the tree. Compilers produce pre-order representations of ASTs for code generation.

Post-order (Left → Right → Root): Visit both subtrees before the current node. Post-order is natural when a node's processing depends on its children's results — computing directory sizes (sum children first), evaluating expression trees (evaluate operands before operator), freeing memory in C (free children before parent).

Level-order (BFS): Visit nodes level by level, left to right, using a queue. Used for finding shortest paths in unweighted trees, for serializing/deserializing (LeetCode tree format is level-order), and for algorithms that must process nodes by depth.

Complexity: All traversals are O(n) time and O(h) space (for the call stack in recursive DFS, where h is height), or O(w) for BFS where w is the maximum width (which can reach O(n) for a complete tree).

from collections import deque
from typing import List

def inorder(node, result=None):
    if result is None: result = []
    if node:
        inorder(node.left, result)
        result.append(node.val)
        inorder(node.right, result)
    return result

def preorder(node, result=None):
    if result is None: result = []
    if node:
        result.append(node.val)
        preorder(node.left, result)
        preorder(node.right, result)
    return result

def postorder(node, result=None):
    if result is None: result = []
    if node:
        postorder(node.left, result)
        postorder(node.right, result)
        result.append(node.val)
    return result

def level_order(root) -> List[List[int]]:
    """Returns list of levels, each level is a list of values."""
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

A Binary Search Tree is a binary tree with one crucial invariant that must hold at every node, not just the root:

For every node N:

• Every value in N's left subtree is strictly less than N's value.
• Every value in N's right subtree is strictly greater than N's value.

This is the BST property, and it must hold recursively throughout the entire tree — not just between a parent and its immediate children.

The power of this invariant: At every node, you can make a binary decision — go left or go right — that eliminates half the remaining candidates (when the tree is balanced). This is exactly how binary search works on a sorted array, but now it works on a dynamic set that supports efficient insertion and deletion.

A common mistake: Students often check only parent-child relationships. Consider a node with value 10, its right child 15, and 15's left child 3. The pair (15, 3) satisfies the local rule (3 < 15) but violates the BST property because 3 is in the right subtree of 10, yet 3 < 10. The invariant must be global.

Verifying a BST correctly: The right approach passes a valid range [min, max] down the tree. Every node's value must fall strictly within this range, narrowed at each step.

def is_bst(node, min_val=float('-inf'), max_val=float('inf')) -> bool:
    """
    Verify the BST property using range propagation.
    At each node, the value must be strictly within (min_val, max_val).
    """
    if node is None:
        return True
    if not (min_val < node.val < max_val):
        return False
    # Going left: the current node's value becomes the new upper bound.
    # Going right: the current node's value becomes the new lower bound.
    return (is_bst(node.left,  min_val, node.val) and
            is_bst(node.right, node.val, max_val))

Searching a BST is elegantly simple because the invariant tells you at every node exactly which subtree can possibly contain the target — you never need to search both.

Algorithm:

1. If the tree is empty, the key is not present → return None.
2. If the current node's value equals the target, found it → return the node.
3. If target < current value, recurse into the left subtree (all right-subtree values are greater than current, so they're all greater than target too).
4. If target > current value, recurse into the right subtree.

Complexity: O(h) where h is the height of the tree. In the best case (perfectly balanced), h = ⌊log₂ n⌋, giving O(log n). In the worst case (a path/chain), h = n - 1, giving O(n).

The iterative version avoids stack overhead and is preferred in practice:

def search(root, key):
    """Iterative BST search. Returns node or None."""
    current = root
    while current is not None:
        if key == current.val:
            return current       # found
        elif key < current.val:
            current = current.left
        else:
            current = current.right
    return None                  # not found

# Recursive version — identical logic, elegant for reasoning about correctness:
def search_rec(node, key):
    if node is None or node.val == key:
        return node
    if key < node.val:
        return search_rec(node.left, key)
    return search_rec(node.right, key)

Insertion follows the same logic as search — navigate to the position where the new key would be found if it existed, then attach the new node there. The BST invariant guarantees there is exactly one correct position for any given key.

Algorithm:

1. If the tree is empty, the new node becomes the root.
2. Navigate exactly as in search — go left if key < current, go right if key > current.
3. When you reach a None child, that gap is the correct insertion point.
4. Attach the new node there.

Key insight: New nodes are always inserted as leaves. This is a remarkable property — you never need to restructure the existing tree for a standard (unbalanced) BST insertion.

Complexity: O(h) — same as search, since we're doing search plus one leaf attachment.

Duplicates: The standard definition excludes duplicates (strict inequalities). In practice, many BSTs adopt a convention (e.g., duplicates go right, or a count field at each node). Be explicit about your convention.

def insert(root, key):
    """
    Recursive BST insertion. Returns the (possibly new) root.
    This functional style is clean for recursion; iterative is fine too.
    """
    if root is None:
        return Node(key)             # base case: insert here as a new leaf
    if key < root.val:
        root.left  = insert(root.left,  key)
    elif key > root.val:
        root.right = insert(root.right, key)
    # key == root.val: ignore duplicate (or handle per your convention)
    return root

# Example: building a BST from a list
def build_bst(values):
    root = None
    for v in values:
        root = insert(root, v)
    return root

# Inserting [5, 3, 7, 1, 4] produces:
#       5
#      / \
#     3   7
#    / \
#   1   4

Deletion is the trickiest BST operation because removing a node can break the tree's structure. There are exactly three cases, and only the third requires real thought.

Case 1: The node to delete is a leaf. Simply remove it — set the parent's pointer to None. No structural issues.

Case 2: The node has exactly one child. Bypass the node by connecting its parent directly to its one child. Like removing a link in a chain.

Case 3: The node has two children. This is the interesting case. You cannot simply remove it — its position in the tree is load-bearing for the BST invariant. The classic solution: replace the node's value with its in-order successor (the smallest value in its right subtree, i.e., the leftmost node in the right subtree), then delete that successor node from the right subtree. The successor has at most one child (no left child, by definition of being the leftmost), so deleting it falls into Case 1 or Case 2.

Why the in-order successor? It is the smallest value greater than the deleted node — it can legally occupy the deleted node's position without violating the BST property for any ancestor or descendant. You can also use the in-order predecessor (largest value in the left subtree) — it's symmetric.

Complexity: O(h) — we search for the node O(h), possibly search for the successor O(h), and perform a deletion O(1). Total O(h).

def delete(root, key):
    """Delete key from BST rooted at root. Returns new root."""
    if root is None:
        return None                     # key not found

    if key < root.val:
        root.left  = delete(root.left,  key)
    elif key > root.val:
        root.right = delete(root.right, key)
    else:
        # Found the node to delete.
        if root.left is None:           # Case 1 or Case 2 (no left child)
            return root.right
        if root.right is None:          # Case 2 (no right child)
            return root.left

        # Case 3: two children
        # Find in-order successor: leftmost node in right subtree
        successor = root.right
        while successor.left is not None:
            successor = successor.left

        # Replace current value with successor's value
        root.val = successor.val

        # Delete the successor from the right subtree
        root.right = delete(root.right, successor.val)

    return root

The BST invariant makes several operations trivially O(h):

Minimum: Always in the leftmost node. Keep going left until you can't.

Maximum: Always in the rightmost node. Keep going right until you can't.

In-order successor of a node N: The next larger value after N in the sorted order. Two cases:

• If N has a right child: the successor is the minimum of N's right subtree (leftmost node in that subtree).
• If N has no right child: walk up the ancestor chain until you find the first ancestor for which N is in its left subtree. That ancestor is the successor. (If none, N is the maximum — no successor.)

In-order predecessor of a node N: Symmetric — the largest value smaller than N.

• If N has a left child: predecessor = maximum of N's left subtree.
• If N has no left child: walk up until you find the first ancestor for which N is in its right subtree.

These operations underpin range queries, sorted iteration, and the deletion algorithm above. In a fully linked BST (with parent pointers), finding the successor takes O(h) worst-case but amortizes to O(1) per step during a full in-order traversal.

def minimum(node):
    """Return node with minimum value in subtree rooted at node."""
    if node is None:
        raise ValueError("Empty tree")
    while node.left is not None:
        node = node.left
    return node

def maximum(node):
    if node is None:
        raise ValueError("Empty tree")
    while node.right is not None:
        node = node.right
    return node

def inorder_successor(root, target_val):
    """
    Find in-order successor of target_val in BST rooted at root.
    Returns successor node or None.
    """
    successor = None
    current = root
    while current:
        if target_val < current.val:
            successor = current      # current could be the answer
            current = current.left
        elif target_val > current.val:
            current = current.right
        else:
            # Found the node. If it has a right subtree, successor is
            # the minimum of that subtree.
            if current.right:
                return minimum(current.right)
            break
    return successor

Here lies the fatal flaw of the naive BST — and the motivating insight for everything that follows in the study of balanced trees.

The key insight: The performance of all BST operations (search, insert, delete) is O(h), where h is the height. If the tree is balanced, h = Θ(log n), which is optimal. But the BST property says nothing about balance — it only constrains the ordering of values, not the shape of the tree.

The degenerate case: Insert values in sorted order into a BST: 1, 2, 3, 4, 5, ..., n. At each step, the new value is the largest yet, so it always goes to the right child of the previous rightmost node. The tree becomes a chain — effectively a linked list leaning right. Height = n-1. All operations are now O(n), no better than linear scan.

Worst cases:

• Sorted ascending input → right-leaning chain.
• Sorted descending input → left-leaning chain.
• Alternating largest/smallest → a zigzag chain, still O(n) height.

Average case with random input: If the n insertions arrive in a uniformly random order (all n! permutations equally likely), the expected height is approximately 4.311 ln n ≈ O(log n). But "random" input is rare in practice — data is often nearly sorted (timestamps, sequential IDs), making degradation the expected outcome, not the exception.

Measuring imbalance — the balance factor: For a node N, its balance factor = height(N.right) - height(N.left). In a perfectly balanced tree, all balance factors are 0 or ±1. In a degenerate chain, balance factors grow linearly.

This analysis is why AVL trees, red-black trees, and B-trees exist: they enforce a structural invariant (beyond the ordering invariant) that keeps height bounded at O(log n) even for adversarial input sequences.

# Demonstration of BST degradation
def demo_degradation(n=10):
    """
    Insert 1..n in sorted order and observe the height.
    A balanced tree of 10 nodes should have height ~3.
    A degenerate BST of 10 nodes has height 9.
    """
    root = None
    for i in range(1, n + 1):
        root = insert(root, i)
    h = height(root)
    print(f"n={n}, height={h}")  # prints: n=10, height=9
    # Optimal height for n=10 is floor(log2(10)) = 3
    # Degenerate height for n=10 is 9 = n-1
    return h

# Compare with random insertion order
import random
def demo_random(n=1000):
    vals = list(range(1, n + 1))
    random.shuffle(vals)
    root = None
    for v in vals:
        root = insert(root, v)
    return height(root)   # typically ~14-16 for n=1000 (log2(1000)~10)

Given a sorted array, you can construct the most balanced possible BST in O(n) time using a divide-and-conquer approach: always pick the middle element as the root, recurse on the left half for the left subtree, and recurse on the right half for the right subtree.

This is the static analogue of what AVL and red-black trees do dynamically during insertions. It's useful for:

• Building a BST from a sorted file or database result.
• Re-balancing a degenerate BST: in-order traversal to get sorted array, then reconstruct.
• Demonstrating that balance is achievable — the question is how to maintain it under mutations.

Height of the result: ⌈log₂(n+1)⌉ - 1, which is the minimum possible height for a BST with n nodes.

This also illustrates the deep connection between binary search on arrays and BSTs: a BST built this way encodes exactly the decision tree of binary search. The root is the element you'd compare first in binary search, its children are the elements you'd compare next in each half, and so on.

def sorted_array_to_bst(arr):
    """
    Build the most balanced BST from a sorted array.
    Time: O(n), Space: O(log n) call stack.
    """
    if not arr:
        return None
    mid = len(arr) // 2
    root = Node(arr[mid])
    root.left  = sorted_array_to_bst(arr[:mid])
    root.right = sorted_array_to_bst(arr[mid+1:])
    return root

# For arr = [1,2,3,4,5,6,7]:
#         4
#       /   \
#      2     6
#     / \   / \
#    1   3 5   7
# Height = 2 = floor(log2(7))

A plain BST supports more than just find/insert/delete. The BST invariant enables an entire family of order-based queries that are impossible (or slow) on hash tables:

Range queries: Find all values in [lo, hi]. Navigate the BST; at each node, if the value is in range emit it; if lo < current recurse left; if hi > current recurse right. Time O(k + h) where k is the number of results.

Floor (predecessor query): Find the largest value ≤ x. Navigate as in search; whenever you go right (because x > current), record current as a candidate floor.

Ceiling (successor query): Find the smallest value ≥ x. Symmetric — record candidates when going left.

Rank: How many elements are ≤ x? This requires augmenting each node with the size of its subtree — a technique called order-statistics trees (CLRS Chapter 14). With size augmentation, rank queries are O(h).

Select: Find the element of rank k (the k-th smallest). Also O(h) with size augmentation.

These operations are why databases use BST-derived structures (B-trees) for indexing rather than hash tables: SQL queries like WHERE salary BETWEEN 50000 AND 80000 require range scans that hash tables cannot support efficiently. The BST's ordered structure is precisely what enables this.

This family of operations is a preview of why augmented BSTs — red-black trees with extra fields — appear in the Linux kernel's struct rb_root for tracking memory intervals, timers, and file descriptors.

def range_query(node, lo, hi, result=None):
    """
    Collect all values in [lo, hi] from BST.
    Time: O(k + h) where k = number of results.
    """
    if result is None: result = []
    if node is None:
        return result
    if lo < node.val:              # there may be valid values to the left
        range_query(node.left, lo, hi, result)
    if lo <= node.val <= hi:       # current node is in range
        result.append(node.val)
    if node.val < hi:              # there may be valid values to the right
        range_query(node.right, lo, hi, result)
    return result

def floor_bst(root, x):
    """Largest value <= x in the BST, or None."""
    candidate = None
    node = root
    while node:
        if node.val == x:
            return x
        elif node.val < x:
            candidate = node.val   # this is a valid floor candidate
            node = node.right      # try to find something larger but still <= x
        else:
            node = node.left       # current value too large, go left
    return candidate