← Back to Tutorial Index

Chapter 4: Trees & Binary Trees

Master tree traversals (DFS, BFS), Binary Search Trees, tree construction, and common tree algorithms. Learn when and where to use each technique.

1. Tree Fundamentals

📌 When and Where to Use

  • Hierarchical data: Representing hierarchical relationships
  • Search operations: Binary Search Trees for O(log n) search
  • Decision making: Decision trees in AI/ML
  • Real-world example: File systems, organization charts, HTML DOM, expression trees, or database indexes

Tree Node Structure

class TreeNode:
    """Node in a binary tree"""
    def __init__(self, val=0, left=None, right=None):
        # Step 1: Store the value
        self.val = val
        # Step 2: Store reference to left child
        self.left = left
        # Step 3: Store reference to right child
        self.right = right

Step-by-Step Explanation:

Step 1 - Value: Each node stores a value.
Step 2 - Left Child: Reference to left subtree (None if no left child).
Step 3 - Right Child: Reference to right subtree (None if no right child).

2. DFS Traversals (Inorder, Preorder, Postorder)

Inorder Traversal (Left, Root, Right)

def inorder_traversal(root):
    """
    Inorder traversal: Left → Root → Right
    For BST: Returns nodes in sorted order
    
    Args:
        root: Root node of binary tree
    
    Returns:
        List of node values in inorder
    """
    result = []
    
    def dfs(node):
        # Step 1: Base case - if node is None, return
        if node is None:
            return
        
        # Step 2: Traverse left subtree first
        dfs(node.left)
        
        # Step 3: Process current node (root)
        result.append(node.val)
        
        # Step 4: Traverse right subtree
        dfs(node.right)
    
    # Step 5: Start traversal from root
    dfs(root)
    return result

Step-by-Step Code Walkthrough:

Step 1 - Base Case: If node is None, we've reached a leaf's child → return.
Step 2 - Left: Recursively traverse left subtree first.
Step 3 - Root: Process current node (add to result).
Step 4 - Right: Recursively traverse right subtree.
Step 5 - Start: Begin traversal from root.
Key Property: For BST, inorder gives sorted order!

Preorder Traversal (Root, Left, Right)

def preorder_traversal(root):
    """
    Preorder traversal: Root → Left → Right
    Useful for copying tree structure
    
    Args:
        root: Root node of binary tree
    
    Returns:
        List of node values in preorder
    """
    result = []
    
    def dfs(node):
        if node is None:
            return
        
        # Step 1: Process root first
        result.append(node.val)
        
        # Step 2: Then left subtree
        dfs(node.left)
        
        # Step 3: Then right subtree
        dfs(node.right)
    
    dfs(root)
    return result

Postorder Traversal (Left, Right, Root)

def postorder_traversal(root):
    """
    Postorder traversal: Left → Right → Root
    Useful for deleting tree (process children before parent)
    
    Args:
        root: Root node of binary tree
    
    Returns:
        List of node values in postorder
    """
    result = []
    
    def dfs(node):
        if node is None:
            return
        
        # Step 1: Traverse left first
        dfs(node.left)
        
        # Step 2: Then right
        dfs(node.right)
        
        # Step 3: Process root last
        result.append(node.val)
    
    dfs(root)
    return result

3. Binary Search Tree (BST)

📌 When and Where to Use

  • Ordered data: When you need sorted data with efficient search
  • Range queries: Finding all elements in a range
  • Dynamic sets: Insert/delete/search operations
  • Real-world example: Database indexes, priority queues, symbol tables, or maintaining sorted data with insertions

BST Property

For every node:

  • All nodes in left subtree have values < node.val
  • All nodes in right subtree have values > node.val

Example: Search in BST

def search_bst(root, val):
    """
    Search for value in Binary Search Tree.
    
    Args:
        root: Root node of BST
        val: Value to search for
    
    Returns:
        Node containing val, or None if not found
    """
    # Step 1: Base case - empty tree or found
    if root is None or root.val == val:
        return root
    
    # Step 2: Compare with current node
    if val < root.val:
        # Step 3: Search left subtree
        # Value is smaller, must be in left subtree
        return search_bst(root.left, val)
    else:
        # Step 4: Search right subtree
        # Value is larger, must be in right subtree
        return search_bst(root.right, val)

Step-by-Step Code Walkthrough:

Step 1 - Base Case: If root is None (not found) or root.val == val (found), return.
Step 2 - Compare: Compare val with current node's value.
Step 3 - Left: If val < root.val, search left subtree (BST property).
Step 4 - Right: If val > root.val, search right subtree (BST property).
Time Complexity: O(h) where h is height. O(log n) for balanced tree, O(n) worst case.

4. Validate Binary Search Tree

Example: Check if Tree is Valid BST

def is_valid_bst(root):
    """
    Validate if binary tree is a valid BST.
    
    Args:
        root: Root node of binary tree
    
    Returns:
        True if valid BST, False otherwise
    """
    def validate(node, min_val, max_val):
        # Step 1: Base case - empty tree is valid
        if node is None:
            return True
        
        # Step 2: Check current node
        # Value must be within (min_val, max_val) range
        if node.val <= min_val or node.val >= max_val:
            return False
        
        # Step 3: Validate left subtree
        # All values in left must be < current node
        # So max_val becomes current node's value
        left_valid = validate(node.left, min_val, node.val)
        
        # Step 4: Validate right subtree
        # All values in right must be > current node
        # So min_val becomes current node's value
        right_valid = validate(node.right, node.val, max_val)
        
        # Step 5: Both subtrees must be valid
        return left_valid and right_valid
    
    # Step 6: Start with infinite range
    # Use float('inf') to represent no upper/lower bound initially
    return validate(root, float('-inf'), float('inf'))

Step-by-Step Code Walkthrough:

Step 1 - Base Case: Empty tree is valid BST.
Step 2 - Check Range: Current node's value must be strictly between min_val and max_val.
Step 3 - Left Subtree: Validate left with updated max_val = node.val (all left values must be < node.val).
Step 4 - Right Subtree: Validate right with updated min_val = node.val (all right values must be > node.val).
Step 5 - Combine: Both subtrees must be valid.
Step 6 - Initialize: Start with infinite range (no constraints initially).

5. Lowest Common Ancestor (LCA)

📌 When and Where to Use

  • Tree queries: Finding common ancestor of two nodes
  • Path problems: Finding distance between nodes
  • Real-world example: Finding common manager in org chart, finding common parent in file system, or Git merge base

Example: Find LCA in Binary Tree

def lowest_common_ancestor(root, p, q):
    """
    Find lowest common ancestor of two nodes in binary tree.
    
    Args:
        root: Root node of binary tree
        p: First node
        q: Second node
    
    Returns:
        Lowest common ancestor node
    """
    # Step 1: Base case
    if root is None or root == p or root == q:
        # If we found p or q, return it
        # This node might be the LCA
        return root
    
    # Step 2: Search in left subtree
    left = lowest_common_ancestor(root.left, p, q)
    
    # Step 3: Search in right subtree
    right = lowest_common_ancestor(root.right, p, q)
    
    # Step 4: Analyze results
    if left and right:
        # Step 4a: Both found in different subtrees
        # Current root is the LCA
        return root
    elif left:
        # Step 4b: Found in left subtree
        # LCA is in left subtree
        return left
    else:
        # Step 4c: Found in right subtree (or not found)
        # LCA is in right subtree, or None if not found
        return right

Step-by-Step Code Walkthrough:

Step 1 - Base Case: If root is None or equals p or q, return root (found one of the nodes).
Step 2 - Search Left: Recursively search for p and q in left subtree.
Step 3 - Search Right: Recursively search for p and q in right subtree.
Step 4 - Analyze:
  • Step 4a: If both left and right return non-None, p and q are in different subtrees → current root is LCA!
  • Step 4b: If only left returns non-None, LCA is in left subtree
  • Step 4c: Otherwise, LCA is in right subtree (or not found)

6. Construct Binary Tree from Preorder and Inorder

Example: Build Tree from Traversals

def build_tree(preorder, inorder):
    """
    Construct binary tree from preorder and inorder traversals.
    
    Args:
        preorder: List of values in preorder
        inorder: List of values in inorder
    
    Returns:
        Root node of constructed tree
    """
    # Step 1: Base case
    if not preorder or not inorder:
        return None
    
    # Step 2: Root is first element in preorder
    # Preorder: Root → Left → Right
    root_val = preorder[0]
    root = TreeNode(root_val)
    
    # Step 3: Find root position in inorder
    # Inorder: Left → Root → Right
    root_idx = inorder.index(root_val)
    
    # Step 4: Split inorder into left and right
    # Left subtree: elements before root in inorder
    left_inorder = inorder[:root_idx]
    # Right subtree: elements after root in inorder
    right_inorder = inorder[root_idx + 1:]
    
    # Step 5: Split preorder (skip root, match sizes)
    # Left preorder: next len(left_inorder) elements
    left_preorder = preorder[1:1 + len(left_inorder)]
    # Right preorder: remaining elements
    right_preorder = preorder[1 + len(left_inorder):]
    
    # Step 6: Recursively build subtrees
    root.left = build_tree(left_preorder, left_inorder)
    root.right = build_tree(right_preorder, right_inorder)
    
    return root

Step-by-Step Code Walkthrough:

Step 1 - Base Case: If either list is empty, return None.
Step 2 - Root: First element in preorder is the root (preorder starts with root).
Step 3 - Find Root: Locate root's position in inorder to split left/right subtrees.
Step 4 - Split Inorder:
  • Left: elements before root
  • Right: elements after root
Step 5 - Split Preorder: Match sizes with inorder splits (skip root, take appropriate lengths).
Step 6 - Recurse: Recursively build left and right subtrees.

📚 Chapter Summary

  • DFS Traversals: Inorder (sorted for BST), Preorder (copy tree), Postorder (delete tree)
  • BST: Left < Root < Right property enables O(log n) search
  • LCA: Use recursive search, LCA is where both nodes found in different subtrees
  • Tree Construction: Use preorder for root, inorder to split left/right

Key Takeaway: Most tree problems use recursion. The key is understanding tree properties (BST, complete, balanced) and choosing the right traversal order.

← Previous: Chapter 1 Next: Chapter 3 - Dynamic Programming →