7. Trees

What Is a Tree?

A tree is a hierarchical data structure where nodes are connected in a parent-child relationship. It's like a family tree — one root at the top, branches below, leaves at the bottom. There are no cycles.

Real-world trees:

• File system — directories (internal nodes) and files (leaves)
• HTML/DOM — nested elements
• JSON/XML — nested data
• Database indexes — B-trees for fast lookups
• Company org chart — CEO → VPs → Managers → ICs

---

7.1 Binary Tree

Each node has at most two children: left and right.

class TreeNode:
    def __init__(self, val: int):
        self.val   = val
        self.left: "TreeNode | None"  = None
        self.right: "TreeNode | None" = None

# Build a simple tree:
#        1
#       / \
#      2   3
#     / \
#    4   5
root        = TreeNode(1)
root.left   = TreeNode(2)
root.right  = TreeNode(3)
root.left.left  = TreeNode(4)
root.left.right = TreeNode(5)

---

7.2 Tree Traversals

Three ways to visit all nodes, depending on when you process the current node:

# --- Inorder (Left → Node → Right) ---
# For a BST: produces nodes in sorted order
def inorder(root: TreeNode | None) -> list[int]:
    if root is None:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# --- Preorder (Node → Left → Right) ---
# Useful for copying a tree or serializing its structure
def preorder(root: TreeNode | None) -> list[int]:
    if root is None:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# --- Postorder (Left → Right → Node) ---
# Useful for deleting a tree (children before parent)
def postorder(root: TreeNode | None) -> list[int]:
    if root is None:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

# --- Level order / BFS (level by level) ---
# Useful when you care about depth (e.g., minimum depth, level-wise operations)
from collections import deque

def level_order(root: TreeNode | None) -> list[list[int]]:
    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

print(inorder(root))       # [4, 2, 5, 1, 3]
print(preorder(root))      # [1, 2, 4, 5, 3]
print(postorder(root))     # [4, 5, 2, 3, 1]
print(level_order(root))   # [[1], [2, 3], [4, 5]]

---

7.3 Binary Search Tree (BST)

A BST maintains the BST property: every node's left subtree has smaller values, right subtree has larger values.

This gives $O(\log n)$ search, insert, delete — for balanced trees. Worst case (fully skewed) is $O(n)$.

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

    def insert(self, val: int) -> None:
        self.root = self._insert(self.root, val)

    def _insert(self, node: TreeNode | None, val: int) -> TreeNode:
        if node is None:
            return TreeNode(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        # val == node.val → no duplicates (or handle as needed)
        return node

    def search(self, val: int) -> bool:
        cur = self.root
        while cur:
            if val == cur.val:
                return True
            cur = cur.left if val < cur.val else cur.right
        return False

# Usage
bst = BST()
for v in [5, 3, 7, 1, 4, 6, 8]:
    bst.insert(v)
print(bst.search(4))   # True
print(bst.search(9))   # False
# Inorder gives sorted output: 1 3 4 5 6 7 8

---

7.4 Common Tree Algorithms

# --- Height of a tree ---
def height(root: TreeNode | None) -> int:
    if root is None:
        return 0
    return 1 + max(height(root.left), height(root.right))

# --- Count total nodes ---
def count_nodes(root: TreeNode | None) -> int:
    if root is None:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

# --- Check if a tree is symmetric (mirror image) ---
def is_symmetric(root: TreeNode | None) -> bool:
    def mirrors(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        return (left.val == right.val
                and mirrors(left.left, right.right)
                and mirrors(left.right, right.left))
    return mirrors(root, root)

# --- Path from root to target value ---
def find_path(root: TreeNode | None, target: int) -> list[int]:
    if root is None:
        return []
    if root.val == target:
        return [root.val]
    for child in [root.left, root.right]:
        path = find_path(child, target)
        if path:
            return [root.val] + path
    return []

print(find_path(root, 4))   # [1, 2, 4]

---