Trees

Tree Fundamentals

A tree is a fundamental hierarchical data structure consisting of nodes connected by edges. Unlike linear data structures (arrays, linked lists), trees represent relationships in a parent-child hierarchy, making them ideal for representing hierarchical data, organizing information, and implementing efficient search and retrieval operations.

Key Terminology

  • Node: A fundamental unit containing data and references to child nodes
  • Root: The topmost node in a tree (has no parent)
  • Parent: A node that has child nodes
  • Child: A node directly connected to a parent node
  • Leaf: A node with no children (also called external node)
  • Internal Node: A node with at least one child
  • Edge: Connection between two nodes
  • Path: Sequence of nodes connected by edges
  • Depth: Number of edges from the root down to a node. The root has depth 0.
  • Height: Number of edges on the longest path from a node down to a leaf. A leaf has height 0; the height of the tree is the height of its root.
  • Level: All nodes at the same depth
  • Subtree: A tree formed by a node and all its descendants
  • Ancestor: Any node on the path from root to a given node
  • Descendant: Any node in the subtree rooted at a given node
  • Sibling: Nodes with the same parent

Tree Properties

  • A tree with n nodes has exactly n-1 edges
  • There is exactly one path between any two nodes
  • Adding any edge creates a cycle (no longer a tree)
  • Removing any edge disconnects the tree
  • A tree is a connected acyclic graph

Watch the counting convention. Height and depth are defined above in edges, the standard in CLRS — a single-node tree has height 0 and an empty tree has height −1, which is what tree_height below returns. But many implementations, including max_depth later on this page and most LeetCode problems, count nodes: a single node has depth 1, an empty tree 0. Both conventions are common, they differ by exactly one, and mixing them is a reliable source of off-by-one bugs. When reading any height function, check its empty-tree base case first — return -1 or return 0 tells you which convention is in force.

Basic Tree Implementation

class TreeNode:
    def __init__(self, val=0, children=None):
        self.val = val
        self.children = children if children is not None else []

# Example: Creating a tree
root = TreeNode(1)
root.children = [TreeNode(2), TreeNode(3), TreeNode(4)]
root.children[0].children = [TreeNode(5), TreeNode(6)]

# Tree structure:
#       1
#     / | \
#    2  3  4
#   / \
#  5   6

Tree Height and Depth Calculation

def tree_height(root):
    """Calculate the height of a tree (maximum depth)"""
    if not root:
        return -1  # Empty tree has height -1, single node has height 0
    
    if not root.children:  # Leaf node
        return 0
    
    # Height is 1 + maximum height of all subtrees
    return 1 + max(tree_height(child) for child in root.children)

def node_depth(root, target, depth=0):
    """Find the depth of a specific node"""
    if not root:
        return -1
    
    if root.val == target:
        return depth
    
    # Search in all children
    for child in root.children:
        result = node_depth(child, target, depth + 1)
        if result != -1:
            return result
    
    return -1  # Node not found

Types of Trees

  • General Tree: No restriction on number of children per node
  • Binary Tree: Each node has at most 2 children
  • Binary Search Tree (BST): Binary tree with ordering property
  • AVL Tree: Self-balancing BST
  • Red-Black Tree: Self-balancing BST with color properties
  • Heap: Complete binary tree with heap property
  • Trie: Prefix tree for string operations
  • B-Tree: Multi-way search tree for databases

Binary Trees

A binary tree is a tree data structure where each node has at most two children, referred to as the left child and right child. Binary trees are fundamental in computer science and form the basis for many advanced data structures like binary search trees, heaps, and expression trees.

Binary Tree Structure

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

# Example binary tree:
#        1
#       / \
#      2   3
#     / \   \
#    4   5   6

Types of Binary Trees

1. Full Binary Tree

Every node has either 0 or 2 children (no node has exactly 1 child). 

# Full binary tree example:
#        1
#       / \
#      2   3
#     / \
#    4   5

2. Complete Binary Tree

All levels are completely filled except possibly the last level, which is filled from left to right. Used in heaps. 

# Complete binary tree example:
#        1
#       / \
#      2   3
#     / \ /
#    4  5 6

3. Perfect Binary Tree

All internal nodes have exactly 2 children, and all leaves are at the same level. A perfect binary tree of height h has 2h+1 - 1 nodes. 

# Perfect binary tree example:
#        1
#       / \
#      2   3
#     / \ / \
#    4  5 6  7

4. Balanced Binary Tree

The height difference between left and right subtrees of any node is at most 1. Ensures O(log n) operations.

5. Degenerate (Pathological) Tree

Each parent node has only one child, essentially a linked list. Worst case for tree operations (O(n)). 

# Degenerate tree (worst case):
#    1
#     \
#      2
#       \
#        3
#         \
#          4

Binary Tree Properties

  • Maximum number of nodes at level l: 2l
  • Maximum number of nodes in a binary tree of height h: 2h+1 - 1
  • Minimum number of nodes in a binary tree of height h: h + 1
  • Number of leaf nodes in a full binary tree: (n + 1) / 2
  • Number of internal nodes in a full binary tree: (n - 1) / 2

Common Binary Tree Operations

Count Nodes

def count_nodes(root):
    """Count total number of nodes in binary tree"""
    if not root:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

Count Leaf Nodes

def count_leaves(root):
    """Count number of leaf nodes"""
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    return count_leaves(root.left) + count_leaves(root.right)

Maximum Depth/Height

def max_depth(root):
    """Calculate maximum depth of binary tree"""
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Check if Balanced

def is_balanced(root):
    """Check if binary tree is balanced"""
    def check_balance(node):
        if not node:
            return 0, True
        
        left_height, left_balanced = check_balance(node.left)
        right_height, right_balanced = check_balance(node.right)
        
        height = 1 + max(left_height, right_height)
        balanced = (left_balanced and right_balanced and 
                   abs(left_height - right_height) <= 1)
        
        return height, balanced
    
    _, balanced = check_balance(root)
    return balanced

Check if Same Tree

def is_same_tree(p, q):
    """Check if two binary trees are identical"""
    if not p and not q:
        return True
    if not p or not q:
        return False
    return (p.val == q.val and 
            is_same_tree(p.left, q.left) and 
            is_same_tree(p.right, q.right))

Check if Symmetric

def is_symmetric(root):
    """Check if binary tree is symmetric (mirror image)"""
    def is_mirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        return (left.val == right.val and 
                is_mirror(left.left, right.right) and 
                is_mirror(left.right, right.left))
    
    if not root:
        return True
    return is_mirror(root.left, root.right)

Invert Binary Tree

def invert_tree(root):
    """Invert (mirror) a binary tree"""
    if not root:
        return None
    
    # Swap left and right subtrees
    root.left, root.right = root.right, root.left
    
    # Recursively invert subtrees
    invert_tree(root.left)
    invert_tree(root.right)
    
    return root

Binary Tree Construction

From Array (Level-order)

def build_tree_from_array(arr):
    """Build binary tree from level-order array representation"""
    if not arr or arr[0] is None:
        return None
    
    root = TreeNode(arr[0])
    queue = deque([root])
    i = 1
    
    while queue and i < len(arr):
        node = queue.popleft()
        
        if i < len(arr) and arr[i] is not None:
            node.left = TreeNode(arr[i])
            queue.append(node.left)
        i += 1
        
        if i < len(arr) and arr[i] is not None:
            node.right = TreeNode(arr[i])
            queue.append(node.right)
        i += 1
    
    return root

From Preorder and Inorder

def build_tree_pre_inorder(preorder, inorder):
    """O(n) construction using an index map and a moving preorder cursor.

    The straightforward version calls inorder.index() and slices both lists at
    every node. index() is a linear scan and each slice copies, so that version
    is O(n^2) time and O(n^2) space - and index() also breaks outright when the
    tree contains duplicate values, since it always finds the first match.
    Precomputing positions and passing bounds instead fixes both.
    """
    position = {val: i for i, val in enumerate(inorder)}   # O(1) root lookup
    pre_idx = 0                                            # cursor into preorder

    def build(left, right):          # inclusive bounds into inorder
        nonlocal pre_idx
        if left > right:
            return None

        root_val = preorder[pre_idx]
        pre_idx += 1
        root = TreeNode(root_val)

        mid = position[root_val]
        root.left  = build(left, mid - 1)      # must build left first:
        root.right = build(mid + 1, right)     # preorder is root, left, right
        return root

    return build(0, len(inorder) - 1)

# Note: this requires DISTINCT values. With duplicates the pair of traversals
# does not determine a unique tree, so the problem itself is ill-posed.

Tree Traversals

Tree traversal is the process of visiting all nodes in a tree exactly once. Different traversal orders serve different purposes: inorder for BST gives sorted order, preorder for copying trees, postorder for deleting trees, and level-order for breadth-first processing.

1. Inorder Traversal (Left → Root → Right)

Visit left subtree, then root, then right subtree. For BST, this produces values in sorted order.

Recursive Implementation

def inorder_traversal(root):
    """Inorder traversal - returns list of values"""
    result = []
    
    def inorder(node):
        if node:
            inorder(node.left)      # Left
            result.append(node.val) # Root
            inorder(node.right)     # Right
    
    inorder(root)
    return result

# Example tree:
#        1
#       / \
#      2   3
#     / \
#    4   5
# Result: [4, 2, 5, 1, 3]

Iterative Implementation

def inorder_iterative(root):
    """Iterative inorder using stack"""
    result = []
    stack = []
    current = root
    
    while stack or current:
        # Go to leftmost node
        while current:
            stack.append(current)
            current = current.left
        
        # Process node
        current = stack.pop()
        result.append(current.val)
        
        # Move to right subtree
        current = current.right
    
    return result

2. Preorder Traversal (Root → Left → Right)

Visit root first, then left subtree, then right subtree. Useful for copying trees, prefix expressions, and serialization.

Recursive Implementation

def preorder_traversal(root):
    """Preorder traversal - returns list of values"""
    result = []
    
    def preorder(node):
        if node:
            result.append(node.val) # Root
            preorder(node.left)     # Left
            preorder(node.right)    # Right
    
    preorder(root)
    return result

# Example tree:
#        1
#       / \
#      2   3
#     / \
#    4   5
# Result: [1, 2, 4, 5, 3]

Iterative Implementation

def preorder_iterative(root):
    """Iterative preorder using stack"""
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        
        # Push right first, then left (so left is processed first)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

3. Postorder Traversal (Left → Right → Root)

Visit left subtree, then right subtree, then root. Useful for deleting trees, postfix expressions, and calculating directory sizes.

Recursive Implementation

def postorder_traversal(root):
    """Postorder traversal - returns list of values"""
    result = []
    
    def postorder(node):
        if node:
            postorder(node.left)    # Left
            postorder(node.right)   # Right
            result.append(node.val) # Root
    
    postorder(root)
    return result

# Example tree:
#        1
#       / \
#      2   3
#     / \
#    4   5
# Result: [4, 5, 2, 3, 1]

Iterative Implementation

def postorder_iterative(root):
    """Iterative postorder using two stacks"""
    if not root:
        return []
    
    stack1 = [root]
    stack2 = []
    
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    
    return [node.val for node in reversed(stack2)]

4. Level-Order Traversal (BFS)

Visit nodes level by level from top to bottom, left to right. Uses a queue for breadth-first search. See Breadth-First Search for BFS details.

Implementation

from collections import deque

def level_order_traversal(root):
    """Level-order (BFS) traversal"""
    if not root:
        return []
    
    result = []
    queue = deque([root])       # deque, not list: list.pop(0) is O(n),
                                # which would make this traversal O(n^2)
    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

# Example tree:
#        1
#       / \
#      2   3
#     / \
#    4   5
# Result: [[1], [2, 3], [4, 5]]

5. Zigzag Level-Order Traversal

Level-order traversal but alternating direction at each level. 

def zigzag_level_order(root):
    """Zigzag level-order traversal"""
    if not root:
        return []
    
    result = []
    queue = deque([root])
    left_to_right = True
    
    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)
        
        if not left_to_right:
            level.reverse()
        result.append(level)
        left_to_right = not left_to_right
    
    return result

6. Morris Traversal (Space-Optimized)

Inorder traversal using O(1) extra space by temporarily modifying the tree structure using threaded binary trees. 

def morris_inorder(root):
    """Morris inorder traversal - O(1) space"""
    result = []
    current = root
    
    while current:
        if not current.left:
            # No left child, visit current and go right
            result.append(current.val)
            current = current.right
        else:
            # Find inorder predecessor
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            
            if not predecessor.right:
                # Make current the right child of predecessor
                predecessor.right = current
                current = current.left
            else:
                # Restore tree structure
                predecessor.right = None
                result.append(current.val)
                current = current.right
    
    return result

Traversal Use Cases

Traversal Use Cases
Inorder BST sorted output, expression evaluation (infix)
Preorder Tree copying, prefix expressions, serialization
Postorder Tree deletion, postfix expressions, directory size calculation
Level-order BFS, printing tree structure, finding level-specific nodes

Binary Search Trees

A Binary Search Tree (BST) is a binary tree with the ordering property: for any node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater than the node's value. This property enables efficient search, insertion, and deletion operations with average time complexity O(log n).

BST Properties

  • Ordering Property: for every node, every value in its entire left subtree is less than the node, and every value in its entire right subtree is greater.
  • Inorder Traversal: Produces values in sorted order
  • Uniqueness: Typically, no duplicate values (or handle with count/frequency)
  • Search Efficiency: O(log n) average, O(n) worst case (degenerate tree)

The property is about subtrees, not children. It is tempting to shorten it to "left child < parent < right child", but that weaker condition is not the BST property, and trees satisfying it need not be BSTs. 

        10
       /  \
      5    15
          /  \
         6    20        <-- 6 < 10, so it sits in the WRONG subtree

Every parent-child pair is locally fine: 6 < 15 and 15 < 20. But a search for 6
turns right at the root and never finds it. This is not a BST.

This is exactly why validation requires threading a (min, max) range down the recursion, as is_valid_bst below does. Checking each node against only its immediate children is the classic wrong answer to this problem.

BST Implementation

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

class BST:
    def __init__(self):
        self.root = None

Search Operation

Search for a value in BST. Compare with root, go left if smaller, right if larger. 

def search(root, val):
    """Search for value in BST - recursive"""
    if not root or root.val == val:
        return root
    
    if val < root.val:
        return search(root.left, val)
    else:
        return search(root.right, val)

def search_iterative(root, val):
    """Search for value in BST - iterative"""
    current = root
    while current:
        if current.val == val:
            return current
        elif val < current.val:
            current = current.left
        else:
            current = current.right
    return None

# Time Complexity: O(log n) average, O(n) worst
# Space Complexity: O(log n) recursive, O(1) iterative

Insert Operation

Insert a new value while maintaining BST property. 

def insert(root, val):
    """Insert value into BST - recursive"""
    if not root:
        return TreeNode(val)
    
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    # If val == root.val, do nothing (or handle duplicates)
    
    return root

def insert_iterative(root, val):
    """Insert value into BST - iterative"""
    if not root:
        return TreeNode(val)
    
    current = root
    while True:
        if val < current.val:
            if not current.left:
                current.left = TreeNode(val)
                break
            current = current.left
        elif val > current.val:
            if not current.right:
                current.right = TreeNode(val)
                break
            current = current.right
        else:
            break  # Value already exists
    
    return root

# Time Complexity: O(log n) average, O(n) worst

Delete Operation

Delete a node from BST. Three cases: node with no children, one child, or two children. 

def delete_node(root, val):
    """Delete node with given value from BST"""
    if not root:
        return root
    
    if val < root.val:
        root.left = delete_node(root.left, val)
    elif val > root.val:
        root.right = delete_node(root.right, val)
    else:
        # Node to delete found
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        else:
            # Node has two children
            # Find inorder successor (smallest in right subtree)
            successor = find_min(root.right)
            root.val = successor.val
            root.right = delete_node(root.right, successor.val)
    
    return root

def find_min(root):
    """Find node with minimum value in BST"""
    while root.left:
        root = root.left
    return root

# Time Complexity: O(log n) average, O(n) worst

BST Validation

Check if a binary tree is a valid BST. 

def is_valid_bst(root):
    """Check if binary tree is valid BST"""
    def validate(node, min_val, max_val):
        if not node:
            return True
        
        if node.val <= min_val or node.val >= max_val:
            return False
        
        return (validate(node.left, min_val, node.val) and 
                validate(node.right, node.val, max_val))
    
    return validate(root, float('-inf'), float('inf'))

# Alternative: Using inorder traversal
def is_valid_bst_inorder(root):
    """Validate BST using inorder traversal property"""
    prev = None
    
    def inorder(node):
        nonlocal prev
        if not node:
            return True
        
        if not inorder(node.left):
            return False
        
        if prev is not None and node.val <= prev:
            return False
        
        prev = node.val
        return inorder(node.right)
    
    return inorder(root)

Find Minimum and Maximum

def find_min_bst(root):
    """Find minimum value in BST"""
    if not root:
        return None
    while root.left:
        root = root.left
    return root.val

def find_max_bst(root):
    """Find maximum value in BST"""
    if not root:
        return None
    while root.right:
        root = root.right
    return root.val

Find Kth Smallest Element

def kth_smallest(root, k):
    """Find kth smallest element in BST using inorder"""
    stack = []
    current = root
    
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        
        current = stack.pop()
        k -= 1
        if k == 0:
            return current.val
        
        current = current.right
    
    return None

Lowest Common Ancestor (LCA) in BST

def lca_bst(root, p, q):
    """Find lowest common ancestor in BST"""
    if not root:
        return None
    
    # Both values are in left subtree
    if p < root.val and q < root.val:
        return lca_bst(root.left, p, q)
    
    # Both values are in right subtree
    if p > root.val and q > root.val:
        return lca_bst(root.right, p, q)
    
    # Current node is LCA
    return root

Range Sum Query

def range_sum_bst(root, low, high):
    """Sum all values in BST within range [low, high]"""
    if not root:
        return 0
    
    if root.val < low:
        return range_sum_bst(root.right, low, high)
    if root.val > high:
        return range_sum_bst(root.left, low, high)
    
    return (root.val + 
            range_sum_bst(root.left, low, high) + 
            range_sum_bst(root.right, low, high))

Convert Sorted Array to BST

def sorted_array_to_bst(nums):
    """Convert sorted array to height-balanced BST"""
    if not nums:
        return None
    
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sorted_array_to_bst(nums[:mid])
    root.right = sorted_array_to_bst(nums[mid + 1:])
    
    return root

BST Complexity Analysis

Operation Average Case Worst Case
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)
Space O(n) O(n)

Self-Balancing BSTs

A plain BST degrades to O(n) when data arrives in sorted order — inserting 1, 2, 3, 4, 5 builds a linked list. Sorted input is extremely common in practice, so this is not a theoretical concern. Self-balancing trees fix it by restructuring after each modification, and they all do it with the same primitive: rotation.

Rotations: the underlying primitive

A rotation rearranges three nodes locally, changing height while preserving the in-order sequence. That invariant is the whole trick — the tree stays a valid BST but gets shallower. 

      y                               x
     / \      right rotate (y)       / \
    x   C     ---------------->     A   y
   / \        <----------------        / \
  A   B        left rotate (x)         B   C

In-order on both sides: A x B y C -- unchanged, so the BST property holds.
Only subtree B changes parent; A and C do not move.
                
def rotate_right(y):
    x = y.left
    y.left = x.right      # B moves across
    x.right = y
    return x              # x is the new subtree root

def rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    return y

AVL Trees

Adelson-Velsky and Landis, 1962 — the first self-balancing BST. Every node stores a balance factor: left subtree height minus right subtree height. The invariant is that it is always −1, 0 or +1. After an insert or delete, walk back toward the root and rebalance any node that falls outside that range.

Four cases, resolved by one or two rotations: 

Left-Left    (bf > 1, inserted into left.left)    -> rotate_right(node)
Right-Right  (bf < -1, inserted into right.right) -> rotate_left(node)
Left-Right   (bf > 1, inserted into left.right)   -> rotate_left(node.left), then
                                                     rotate_right(node)
Right-Left   (bf < -1, inserted into right.left)  -> rotate_right(node.right), then
                                                     rotate_left(node)
                
def height(node):
    return node.height if node else -1

def update_height(node):
    node.height = 1 + max(height(node.left), height(node.right))

def balance_factor(node):
    return height(node.left) - height(node.right) if node else 0

def rebalance(node):
    update_height(node)
    bf = balance_factor(node)

    if bf > 1:                                   # left-heavy
        if balance_factor(node.left) < 0:        # left-right case
            node.left = rotate_left(node.left)
        return rotate_right(node)
    if bf < -1:                                  # right-heavy
        if balance_factor(node.right) > 0:       # right-left case
            node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

def avl_insert(node, val):
    if not node:
        return TreeNode(val)          # node needs a .height attribute, starting at 0
    if val < node.val:
        node.left = avl_insert(node.left, val)
    elif val > node.val:
        node.right = avl_insert(node.right, val)
    else:
        return node                   # duplicate: ignore
    return rebalance(node)

An AVL tree of n nodes has height at most about 1.44 log₂n — tightly balanced, so lookups are fast. The cost is that modifications rebalance more often.

Red-Black Trees

A looser balance condition, and therefore fewer rotations per modification. Each node is coloured red or black, subject to five rules:

  1. Every node is red or black.
  2. The root is black.
  3. All leaves (conceptual null nodes) are black.
  4. A red node's children are both black — never two reds in a row.
  5. Every path from a given node down to any leaf contains the same number of black nodes.

Rules 4 and 5 together force the longest root-to-leaf path to be at most twice the shortest, giving a height bound of 2 log₂(n+1). That is looser than AVL, so lookups are slightly slower — but rebalancing needs at most 2 rotations after an insert and 3 after a delete, whereas AVL deletion can rotate O(log n) times.

Choose by workload: read-heavy favours AVL, write-heavy favours red-black. In practice red-black trees dominate the standard libraries — C++ std::map and std::set, Java's TreeMap and TreeSet, and a great deal of kernel code.

Other Balanced Structures

  • Splay Tree: stores no balance information at all. Every access rotates the touched node up to the root, so recently used items stay shallow. A single operation can cost O(n), but any sequence of m operations costs O(m log n) — O(log n) amortized. Excellent under access locality; unsuitable when you need per-operation guarantees.
  • Treap: each node gets a random priority; the tree is a heap on priority and a BST on key. Randomness keeps it balanced with high probability, and it is markedly easier to implement correctly than red-black.
  • Skip List: not a tree, but solves the same problem using probabilistic layers of linked lists. O(log n) expected, and far easier to make lock-free — which is why Redis uses one for sorted sets.

B-Trees and B+ Trees

Everything above optimises the number of comparisons. B-trees optimise something else: the number of page reads. That is why they, and not red-black trees, sit beneath essentially every database index and filesystem you will ever use.

The reasoning is about hardware. Reading one byte from disk costs about the same as reading 4 KB, because storage is addressed in pages. A binary tree over 106 records is roughly 20 levels deep, and if each node is its own page that is 20 reads. A B-tree instead packs hundreds of keys into each node, sized to exactly one page. At a branching factor of 100, the same 106 records fit in 3 levels — 3 reads instead of 20. 

B-tree of order 5 (up to 4 keys and 5 children per node):

                 [ 20 | 50 ]
                /      |     \
      [5|10|15]   [25|30|40]   [60|70|80|90]

Every leaf sits at the SAME depth - B-trees grow at the root, not the leaves.

A B+ tree refines this: internal nodes hold only routing keys, all values live in the leaves, and the leaves are linked together. Internal nodes therefore fit more keys (higher fan-out, shallower tree), and a range scan becomes a sequential walk along the leaf list instead of repeated descents. PostgreSQL, MySQL/InnoDB, SQLite and NTFS all use B+ trees for their primary indexes.

The main alternative is the LSM tree (log-structured merge tree), which buffers writes in memory and flushes sorted runs to disk, trading read latency for much higher write throughput. RocksDB, LevelDB, Cassandra and ClickHouse are built on it.

Advanced Tree Structures

Trie (Prefix Tree)

A trie is a tree-like data structure for storing strings. Each node represents a character, and paths from root to leaf represent words. Excellent for prefix matching and autocomplete. 

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        """Insert word into trie"""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    
    def search(self, word):
        """Search for complete word"""
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end
    
    def starts_with(self, prefix):
        """Check if any word starts with prefix"""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

# Time Complexity: O(m) per operation, where m is the length of the word.
#   Note this does NOT grow with the number of stored words, unlike a BST's O(log n).
#
# Space Complexity: O(total characters inserted).
#   This implementation uses a dict for children, so a node costs only as much as
#   its actual children. The O(ALPHABET_SIZE * N * M) bound you often see applies
#   to the ARRAY-based variant, which reserves a fixed slot per possible character
#   at every node - faster lookup, far more memory. Shared prefixes are stored
#   once, so a trie over similar words uses much less than the sum of their lengths.

For large static dictionaries, a radix tree (Patricia trie) compresses chains of single-child nodes into a single edge, cutting both node count and pointer chasing.

Segment Tree

A segment tree answers range queries in O(log n) and updates in O(log n). Each node stores an aggregate — a sum here, but min, max or gcd work identically — over a contiguous segment.

The implementation below supports point updates and range queries. Supporting range updates — "add 5 to every element in [l, r)" — efficiently needs lazy propagation: store a pending update at each node and push it down only when a query descends past it. Without it a range update costs O(n log n); with it, O(log n).

For prefix sums specifically, a Fenwick tree (binary indexed tree) does the same job in a fraction of the code and about half the memory. It is less general — it needs an invertible operation, so sums yes, minima no — but prefer it where it applies. 

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.size = 1
        while self.size < self.n:
            self.size *= 2
        self.tree = [0] * (2 * self.size)
        self.build(arr)
    
    def build(self, arr):
        """Build segment tree from array"""
        for i in range(self.n):
            self.tree[self.size + i] = arr[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
    
    def query(self, l, r):
        """Query sum in range [l, r)"""
        l += self.size
        r += self.size
        result = 0
        while l < r:
            if l % 2 == 1:
                result += self.tree[l]
                l += 1
            if r % 2 == 1:
                r -= 1
                result += self.tree[r]
            l //= 2
            r //= 2
        return result
    
    def update(self, index, value):
        """Update value at index"""
        index += self.size
        self.tree[index] = value
        index //= 2
        while index >= 1:
            self.tree[index] = self.tree[2 * index] + self.tree[2 * index + 1]
            index //= 2

Common Tree Problems and Patterns

1. Maximum Path Sum

def max_path_sum(root):
    """Find maximum path sum in binary tree"""
    max_sum = float('-inf')
    
    def dfs(node):
        nonlocal max_sum
        if not node:
            return 0
        
        # Max path from left and right (can be negative)
        left_max = max(0, dfs(node.left))
        right_max = max(0, dfs(node.right))
        
        # Current path sum
        current_sum = node.val + left_max + right_max
        max_sum = max(max_sum, current_sum)
        
        # Return max path from this node (can only use one branch)
        return node.val + max(left_max, right_max)
    
    dfs(root)
    return max_sum

2. Diameter of Binary Tree

def diameter_of_binary_tree(root):
    """Find diameter (longest path between any two nodes)"""
    diameter = 0
    
    def height(node):
        nonlocal diameter
        if not node:
            return 0
        
        left_height = height(node.left)
        right_height = height(node.right)
        
        # Diameter is max of: current diameter, path through current node
        diameter = max(diameter, left_height + right_height)
        
        return 1 + max(left_height, right_height)
    
    height(root)
    return diameter

3. Path Sum Problems

def has_path_sum(root, target_sum):
    """Check if path from root to leaf sums to target"""
    if not root:
        return False
    
    if not root.left and not root.right:
        return root.val == target_sum
    
    return (has_path_sum(root.left, target_sum - root.val) or 
            has_path_sum(root.right, target_sum - root.val))

def path_sum_ii(root, target_sum):
    """Find all paths from root to leaf that sum to target"""
    result = []
    
    def dfs(node, remaining, path):
        if not node:
            return
        
        path.append(node.val)
        
        if not node.left and not node.right and remaining == node.val:
            result.append(path[:])
        else:
            dfs(node.left, remaining - node.val, path)
            dfs(node.right, remaining - node.val, path)
        
        path.pop()
    
    dfs(root, target_sum, [])
    return result

4. Serialize and Deserialize Binary Tree

def serialize(root):
    """Serialize binary tree to string"""
    if not root:
        return "None,"
    return str(root.val) + "," + serialize(root.left) + serialize(root.right)

def deserialize(data):
    """Deserialize string to binary tree"""
    def build_tree(values):
        val = next(values)
        if val == "None":
            return None
        node = TreeNode(int(val))
        node.left = build_tree(values)
        node.right = build_tree(values)
        return node
    
    values = iter(data.split(","))
    return build_tree(values)

5. Binary Tree Right Side View

def right_side_view(root):
    """Return values visible from right side of tree"""
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i == level_size - 1:  # Last node in level
                result.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return result

Practice Problems

Here are recommended problems to practice tree algorithms:

Easy

  • LeetCode 104: Maximum Depth of Binary Tree
  • LeetCode 226: Invert Binary Tree
  • LeetCode 101: Symmetric Tree
  • LeetCode 94: Binary Tree Inorder Traversal
  • LeetCode 108: Convert Sorted Array to BST
  • LeetCode 112: Path Sum

Medium

  • LeetCode 98: Validate Binary Search Tree
  • LeetCode 102: Binary Tree Level Order Traversal
  • LeetCode 105: Construct Binary Tree from Preorder and Inorder
  • LeetCode 236: Lowest Common Ancestor of Binary Tree
  • LeetCode 230: Kth Smallest Element in BST
  • LeetCode 199: Binary Tree Right Side View
  • LeetCode 114: Flatten Binary Tree to Linked List
  • LeetCode 543: Diameter of Binary Tree

Hard

  • LeetCode 124: Binary Tree Maximum Path Sum
  • LeetCode 297: Serialize and Deserialize Binary Tree
  • LeetCode 428: Serialize and Deserialize N-ary Tree
  • LeetCode 208: Implement Trie (Prefix Tree)
  • LeetCode 212: Word Search II (Trie)

Summary

Trees are fundamental hierarchical data structures that enable efficient organization and retrieval of data. Binary trees, with their recursive structure, form the basis for many advanced data structures and algorithms.

Key takeaways:

  • Binary trees have at most two children per node, enabling efficient recursive algorithms
  • Tree traversals (inorder, preorder, postorder, level-order) serve different purposes
  • Binary Search Trees maintain ordering property for O(log n) average operations
  • Self-balancing trees (AVL, Red-Black) guarantee O(log n) worst case, all built on the rotation primitive
  • B-trees and B+ trees optimise for page reads rather than comparisons, which is why databases use them
  • Specialized trees (Trie, Segment Tree, Fenwick Tree) solve domain-specific problems efficiently
  • Many tree problems follow recursive patterns with base cases and recursive cases

Understanding trees is essential for algorithms involving hierarchical data, search operations, and many real-world applications like file systems, databases, and compilers.