Trees and Binary Search Trees

📖 Introduction

Trees are everywhere in software development. File systems, DOM structures, database indexes, decision trees in ML models—understanding trees opened my eyes to how hierarchical data naturally organizes itself.

When I first worked on a project involving expression parsing, trees transformed what seemed like an impossible problem into an elegant recursive solution. The moment tree traversals "clicked" for me was a turning point in my understanding of recursive thinking.

---

🌳 Tree Fundamentals

A tree is a hierarchical data structure with nodes connected by edges, forming a parent-child relationship.

Terminology

class TreeNode:
    """Basic tree node."""
    def __init__(self, val):
        self.val = val
        self.children = []

# Terminology:
# - Root: Node with no parent (top of tree)
# - Leaf: Node with no children (bottom of tree)
# - Parent: Node directly above in hierarchy
# - Child: Node directly below in hierarchy
# - Siblings: Nodes sharing same parent
# - Depth: Distance from root (root depth = 0)
# - Height: Distance to furthest leaf
# - Subtree: A node and all its descendants

Binary Tree

Most common tree variant—each node has at most two children.

from typing import Optional

class TreeNode:
    """Binary tree node."""
    def __init__(self, val: int = 0):
        self.val = val
        self.left: Optional['TreeNode'] = None
        self.right: Optional['TreeNode'] = None


def build_sample_tree() -> TreeNode:
    """
    Builds:
           1
          / \
         2   3
        / \   \
       4   5   6
    """
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.right = TreeNode(6)
    return root

Types of Binary Trees

# Full: Every node has 0 or 2 children
# Complete: All levels full except possibly last, filled left to right
# Perfect: All internal nodes have 2 children, all leaves at same level
# Balanced: Height difference between left and right subtrees ≤ 1

---

🔄 Tree Traversals

Depth-First Search (DFS)

Three ways to traverse with DFS:

from typing import Optional, List

class TreeNode:
    def __init__(self, val: int = 0):
        self.val = val
        self.left: Optional['TreeNode'] = None
        self.right: Optional['TreeNode'] = None


# Preorder: Root -> Left -> Right
# [1, 2, 4, 5, 3]
def preorder_recursive(root: Optional[TreeNode]) -> List[int]:
    """Process current, then left subtree, then right subtree."""
    if not root:
        return []
    return [root.val] + preorder_recursive(root.left) + preorder_recursive(root.right)


def preorder_iterative(root: Optional[TreeNode]) -> List[int]:
    """Iterative using stack."""
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        
        # Push right first so left is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result


# Inorder: Left -> Root -> Right
# [4, 2, 5, 1, 3]
def inorder_recursive(root: Optional[TreeNode]) -> List[int]:
    """Process left subtree, then current, then right subtree."""
    if not root:
        return []
    return inorder_recursive(root.left) + [root.val] + inorder_recursive(root.right)


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


# Postorder: Left -> Right -> Root
# [4, 5, 2, 3, 1]
def postorder_recursive(root: Optional[TreeNode]) -> List[int]:
    """Process left subtree, then right subtree, then current."""
    if not root:
        return []
    return postorder_recursive(root.left) + postorder_recursive(root.right) + [root.val]


def postorder_iterative(root: Optional[TreeNode]) -> List[int]:
    """Iterative using two stacks."""
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    
    return result[::-1]  # Reverse

When to Use Each Traversal

Traversal	Use Case
Preorder	Create copy of tree, prefix expression
Inorder	BST sorted order, expression parsing
Postorder	Delete tree, postfix expression, subtree computations

Breadth-First Search (BFS)

Level by level traversal.

from collections import deque
from typing import List, Optional

def level_order(root: Optional[TreeNode]) -> List[List[int]]:
    """
    Level order traversal.
    Returns: [[1], [2, 3], [4, 5, 6]]
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level = []
        level_size = len(queue)
        
        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


def zigzag_level_order(root: Optional[TreeNode]) -> List[List[int]]:
    """Alternate direction each level."""
    if not root:
        return []
    
    result = []
    queue = deque([root])
    left_to_right = True
    
    while queue:
        level = deque()
        level_size = len(queue)
        
        for _ in range(level_size):
            node = queue.popleft()
            
            if left_to_right:
                level.append(node.val)
            else:
                level.appendleft(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(list(level))
        left_to_right = not left_to_right
    
    return result

---

🔍 Binary Search Tree (BST)

A BST maintains the property: left < root < right.

BST Operations

from typing import Optional

class TreeNode:
    def __init__(self, val: int):
        self.val = val
        self.left: Optional['TreeNode'] = None
        self.right: Optional['TreeNode'] = None


class BST:
    def __init__(self):
        self.root: Optional[TreeNode] = None
    
    def search(self, val: int) -> Optional[TreeNode]:
        """Search for value. O(h) where h is height."""
        node = self.root
        
        while node:
            if val == node.val:
                return node
            elif val < node.val:
                node = node.left
            else:
                node = node.right
        
        return None
    
    def insert(self, val: int) -> TreeNode:
        """Insert value. O(h)."""
        if not self.root:
            self.root = TreeNode(val)
            return self.root
        
        node = self.root
        
        while True:
            if val < node.val:
                if node.left:
                    node = node.left
                else:
                    node.left = TreeNode(val)
                    return node.left
            else:
                if node.right:
                    node = node.right
                else:
                    node.right = TreeNode(val)
                    return node.right
    
    def delete(self, val: int) -> bool:
        """Delete value. O(h)."""
        parent = None
        node = self.root
        is_left = True
        
        # Find node
        while node and node.val != val:
            parent = node
            if val < node.val:
                node = node.left
                is_left = True
            else:
                node = node.right
                is_left = False
        
        if not node:
            return False
        
        # Case 1: Leaf node
        if not node.left and not node.right:
            if not parent:
                self.root = None
            elif is_left:
                parent.left = None
            else:
                parent.right = None
        
        # Case 2: One child
        elif not node.left or not node.right:
            child = node.left or node.right
            if not parent:
                self.root = child
            elif is_left:
                parent.left = child
            else:
                parent.right = child
        
        # Case 3: Two children
        else:
            # Find inorder successor (smallest in right subtree)
            successor_parent = node
            successor = node.right
            
            while successor.left:
                successor_parent = successor
                successor = successor.left
            
            # Replace node value with successor value
            node.val = successor.val
            
            # Delete successor
            if successor_parent == node:
                successor_parent.right = successor.right
            else:
                successor_parent.left = successor.right
        
        return True
    
    def inorder(self) -> list[int]:
        """Inorder traversal gives sorted order."""
        result = []
        
        def traverse(node):
            if not node:
                return
            traverse(node.left)
            result.append(node.val)
            traverse(node.right)
        
        traverse(self.root)
        return result


# Usage
bst = BST()
for val in [8, 3, 10, 1, 6, 14, 9]:
    bst.insert(val)

print(bst.inorder())  # [1, 3, 6, 8, 9, 10, 14]
print(bst.search(6))  # TreeNode(6)
bst.delete(3)
print(bst.inorder())  # [1, 6, 8, 9, 10, 14]

BST Properties

def is_valid_bst(root: Optional[TreeNode]) -> bool:
    """
    Validate BST property.
    Time: O(n), Space: O(h)
    """
    def validate(node, min_val, max_val):
        if not node:
            return True
        
        if not (min_val < 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'))


def kth_smallest(root: Optional[TreeNode], k: int) -> int:
    """Find kth smallest element in BST. O(h + k)."""
    stack = []
    current = root
    count = 0
    
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        
        current = stack.pop()
        count += 1
        
        if count == k:
            return current.val
        
        current = current.right
    
    return -1


def lowest_common_ancestor_bst(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    """
    LCA in BST. O(h).
    Use BST property: both smaller -> go left, both larger -> go right.
    """
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root
    
    return root

---

📊 Common Tree Problems

Maximum Depth

def max_depth(root: Optional[TreeNode]) -> int:
    """
    Find maximum depth of binary tree.
    Time: O(n), Space: O(h)
    """
    if not root:
        return 0
    
    return 1 + max(max_depth(root.left), max_depth(root.right))


def max_depth_iterative(root: Optional[TreeNode]) -> int:
    """BFS approach."""
    if not root:
        return 0
    
    depth = 0
    queue = deque([root])
    
    while queue:
        depth += 1
        level_size = len(queue)
        
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return depth

Same Tree / Symmetric Tree

def is_same_tree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    """Check if two 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))


def is_symmetric(root: Optional[TreeNode]) -> bool:
    """Check if tree is a mirror of itself."""
    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))
    
    return is_mirror(root.left, root.right) if root else True

Invert Binary Tree

def invert_tree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    """
    Invert binary tree (mirror).
    Time: O(n), Space: O(h)
    """
    if not root:
        return None
    
    root.left, root.right = root.right, root.left
    invert_tree(root.left)
    invert_tree(root.right)
    
    return root

Path Sum

def has_path_sum(root: Optional[TreeNode], target_sum: int) -> bool:
    """Check if root-to-leaf path exists with given sum."""
    if not root:
        return False
    
    # Leaf node
    if not root.left and not root.right:
        return root.val == target_sum
    
    remaining = target_sum - root.val
    return (has_path_sum(root.left, remaining) or 
            has_path_sum(root.right, remaining))


def path_sum_ii(root: Optional[TreeNode], target_sum: int) -> List[List[int]]:
    """Find all root-to-leaf paths with given sum."""
    result = []
    
    def dfs(node, remaining, path):
        if not node:
            return
        
        path.append(node.val)
        
        if not node.left and not node.right and node.val == remaining:
            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

Lowest Common Ancestor

def lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    """
    Find LCA of two nodes in binary tree.
    Time: O(n), Space: O(h)
    """
    if not root or root == p or root == q:
        return root
    
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    
    # If both sides return a node, current node is LCA
    if left and right:
        return root
    
    # Return whichever side found something
    return left if left else right

Diameter of Binary Tree

def diameter_of_binary_tree(root: Optional[TreeNode]) -> int:
    """
    Find longest path between any two nodes.
    Time: O(n), Space: O(h)
    """
    diameter = 0
    
    def depth(node):
        nonlocal diameter
        
        if not node:
            return 0
        
        left = depth(node.left)
        right = depth(node.right)
        
        # Update diameter (path through current node)
        diameter = max(diameter, left + right)
        
        return 1 + max(left, right)
    
    depth(root)
    return diameter

Balanced Binary Tree

def is_balanced(root: Optional[TreeNode]) -> bool:
    """
    Check if tree is height-balanced.
    Time: O(n), Space: O(h)
    """
    def check(node):
        if not node:
            return 0
        
        left = check(node.left)
        if left == -1:
            return -1
        
        right = check(node.right)
        if right == -1:
            return -1
        
        if abs(left - right) > 1:
            return -1
        
        return 1 + max(left, right)
    
    return check(root) != -1

Serialize and Deserialize

class Codec:
    """Serialize and deserialize binary tree."""
    
    def serialize(self, root: Optional[TreeNode]) -> str:
        """Preorder with null markers."""
        result = []
        
        def preorder(node):
            if not node:
                result.append("null")
                return
            result.append(str(node.val))
            preorder(node.left)
            preorder(node.right)
        
        preorder(root)
        return ",".join(result)
    
    def deserialize(self, data: str) -> Optional[TreeNode]:
        """Reconstruct from preorder."""
        values = iter(data.split(","))
        
        def build():
            val = next(values)
            if val == "null":
                return None
            
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node
        
        return build()

Build Tree from Traversals

def build_tree_from_preorder_inorder(
    preorder: List[int], 
    inorder: List[int]
) -> Optional[TreeNode]:
    """
    Construct tree from preorder and inorder traversals.
    Time: O(n), Space: O(n)
    """
    if not preorder or not inorder:
        return None
    
    # Create index map for inorder
    inorder_map = {val: idx for idx, val in enumerate(inorder)}
    
    def build(pre_start, pre_end, in_start, in_end):
        if pre_start > pre_end:
            return None
        
        # First element of preorder is root
        root_val = preorder[pre_start]
        root = TreeNode(root_val)
        
        # Find root in inorder
        in_root = inorder_map[root_val]
        left_size = in_root - in_start
        
        root.left = build(
            pre_start + 1, 
            pre_start + left_size,
            in_start, 
            in_root - 1
        )
        
        root.right = build(
            pre_start + left_size + 1, 
            pre_end,
            in_root + 1, 
            in_end
        )
        
        return root
    
    return build(0, len(preorder) - 1, 0, len(inorder) - 1)

---

🌲 Special Tree Types

N-ary Tree

class NaryNode:
    def __init__(self, val=None):
        self.val = val
        self.children = []


def nary_level_order(root: NaryNode) -> List[List[int]]:
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level = []
        level_size = len(queue)
        
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            queue.extend(node.children)
        
        result.append(level)
    
    return result

Trie (Prefix Tree)

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


class Trie:
    """
    Prefix tree for efficient string operations.
    """
    
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        """Insert word. O(m) where m is word length."""
        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: str) -> bool:
        """Search for exact word. O(m)."""
        node = self._find_node(word)
        return node is not None and node.is_end
    
    def starts_with(self, prefix: str) -> bool:
        """Check if any word starts with prefix. O(m)."""
        return self._find_node(prefix) is not None
    
    def _find_node(self, prefix: str) -> Optional[TrieNode]:
        node = self.root
        
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        
        return node


# Usage
trie = Trie()
trie.insert("apple")
trie.insert("app")
print(trie.search("apple"))     # True
print(trie.search("app"))       # True
print(trie.search("ap"))        # False
print(trie.starts_with("ap"))   # True

---

📝 Practice Exercises

Exercise 1: Right Side View

def right_side_view(root: Optional[TreeNode]) -> List[int]:
    """
    Return values visible from right side of tree.
    
    Example:
           1
          / \
         2   3
          \   \
           5   4
    Returns: [1, 3, 4]
    """
    pass

Solution

from collections import deque

def right_side_view(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        
        for i in range(level_size):
            node = queue.popleft()
            
            # Last node in level is visible from right
            if i == level_size - 1:
                result.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return result

Exercise 2: Flatten Binary Tree to Linked List

def flatten(root: Optional[TreeNode]) -> None:
    """
    Flatten tree to linked list in-place using preorder.
    
    Example:
           1          1
          / \          \
         2   5   ->     2
        / \   \          \
       3   4   6          3
                           \
                            4
                             \
                              5
                               \
                                6
    """
    pass

Solution

def flatten(root: Optional[TreeNode]) -> None:
    current = root
    
    while current:
        if current.left:
            # Find rightmost node in left subtree
            rightmost = current.left
            while rightmost.right:
                rightmost = rightmost.right
            
            # Connect to right subtree
            rightmost.right = current.right
            
            # Move left to right
            current.right = current.left
            current.left = None
        
        current = current.right

Exercise 3: Maximum Path Sum

def max_path_sum(root: Optional[TreeNode]) -> int:
    """
    Find maximum path sum. Path can start/end at any node.
    
    Example:
           -10
           /  \
          9   20
             /  \
            15   7
    Returns: 42 (15 -> 20 -> 7)
    """
    pass

Solution

def max_path_sum(root: Optional[TreeNode]) -> int:
    max_sum = float('-inf')
    
    def max_gain(node):
        nonlocal max_sum
        
        if not node:
            return 0
        
        # Maximum gain from left and right (ignore negative)
        left = max(0, max_gain(node.left))
        right = max(0, max_gain(node.right))
        
        # Path through current node
        current_path = node.val + left + right
        max_sum = max(max_sum, current_path)
        
        # Return max gain for parent
        return node.val + max(left, right)
    
    max_gain(root)
    return max_sum

---

🔑 Key Takeaways

1. Trees are hierarchical structures—think recursively

2. DFS (preorder, inorder, postorder) uses stack/recursion

3. BFS uses queue for level-order traversal

4. BST provides O(log n) operations when balanced

5. Inorder traversal of BST gives sorted order

6. Trie is optimal for prefix-based string operations

---

🚀 What's Next?

In the next article, we'll explore heaps and graphs:

• Min/max heap operations

• Priority queue implementation

• Graph representations

• Graph traversal algorithms

Next: Article 9 - Heaps & Graphs

---

📚 References

• CLRS Chapter 12: Binary Search Trees

• CLRS Chapter 10: Basic Tree Concepts

• "Grokking Algorithms" - Trees and Graphs