Complete Guide to Tree Algorithms: Traversals, Construction, and More

Trees are fundamental data structures in computer science. Mastering tree algorithms is essential for technical interviews.

Tree Traversals

Inorder Traversal

Left → Root → Right

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)

Preorder Traversal

Root → Left → Right

def preorder(root):
    if root:
        print(root.val)
        preorder(root.left)
        preorder(root.right)

Postorder Traversal

Left → Right → Root

def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.val)

Level-Order Traversal (BFS)

from collections import deque

def level_order(root):
    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

Common Tree Problems

1. **Maximum Depth:** Find the deepest node

2. **Symmetric Tree:** Check if tree is mirror of itself

3. **Path Sum:** Find paths with target sum

4. **Lowest Common Ancestor:** Find shared ancestor

Trees are everywhere in algorithms - master these patterns!