Understanding Tree Traversals

Tree traversal is a fundamental operation in tree data structures where we visit each node in the tree exactly once. Understanding different traversal methods is crucial for solving tree-related problems efficiently.

Types of Tree Traversals

1. Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. There are three main types:

a) In-order Traversal (Left → Root → Right)

function inorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];
    
    function traverse(node: TreeNode | null) {
        if (!node) return;
        
        traverse(node.left);     // Visit left subtree
        result.push(node.val);   // Visit root
        traverse(node.right);    // Visit right subtree
    }
    
    traverse(root);
    return result;
}

Use Cases:

• Getting nodes in ascending order in a BST
• Converting a BST to a sorted array

b) Pre-order Traversal (Root → Left → Right)

function preorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];
    
    function traverse(node: TreeNode | null) {
        if (!node) return;
        
        result.push(node.val);   // Visit root
        traverse(node.left);     // Visit left subtree
        traverse(node.right);    // Visit right subtree
    }
    
    traverse(root);
    return result;
}

Use Cases:

• Creating a copy of the tree
• Serializing or deserializing a tree
• Getting prefix expression from expression tree

c) Post-order Traversal (Left → Right → Root)

function postorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];
    
    function traverse(node: TreeNode | null) {
        if (!node) return;
        
        traverse(node.left);     // Visit left subtree
        traverse(node.right);    // Visit right subtree
        result.push(node.val);   // Visit root
    }
    
    traverse(root);
    return result;
}

Use Cases:

• Deleting a tree (must process children before parent)
• Computing space used by files in directories
• Evaluating mathematical expression trees

2. Breadth-First Search (BFS)

Also known as Level-Order Traversal, BFS visits all nodes at the current depth before moving to nodes at the next depth level.

function levelOrder(root: TreeNode | null): number[][] {
    if (!root) return [];
    
    const result: number[][] = [];
    const queue: TreeNode[] = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel: number[] = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            currentLevel.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(currentLevel);
    }
    
    return result;
}

Use Cases:

• Finding shortest path between two nodes
• Level-by-level tree processing
• Serializing or deserializing a tree

Time and Space Complexity

For all traversal methods:

• Time Complexity: O(n) where n is the number of nodes
• Space Complexity:
  • O(h) for DFS (recursive) where h is the height of the tree
  • O(w) for BFS where w is the maximum width of the tree

Common Interview Questions

1. Binary Tree Level Order Traversal (LeetCode #102)

   • Use BFS to process tree level by level

2. Validate Binary Search Tree (LeetCode #98)

   • Use in-order traversal to check if values are in ascending order

3. Construct Binary Tree from Preorder and Inorder Traversal (LeetCode #105)

   • Use characteristics of different traversal orders to reconstruct the tree

Best Practices

1. Always Handle Edge Cases

   • Empty tree
   • Single node tree
   • Unbalanced trees

2. Choose the Right Traversal

   • Use in-order for BST when order matters
   • Use pre-order for tree serialization
   • Use post-order when child-before-parent processing is needed
   • Use BFS for level-based operations

3. Consider Iterative vs Recursive

   • Recursive solutions are cleaner but may cause stack overflow
   • Iterative solutions using stack/queue are more space-efficient

Key Takeaways

• Different traversal methods serve different purposes
• Understanding when to use each type is crucial
• Practice implementing both recursive and iterative solutions
• Pay attention to space complexity, especially for large trees