Binary Tree Traversal

Master the fundamental patterns of tree traversal: the gateway to solving hundreds of tree problems in interviews.

Problem

Given the root of a binary tree, return the traversal of its nodes’ values in different orders:

1. Inorder (Left → Root → Right)
2. Preorder (Root → Left → Right)
3. Postorder (Left → Right → Root)
4. Level Order (Level by level, left to right)

Example:

        1
       / \
      2   3
     / \
    4   5

Inorder:    [4, 2, 5, 1, 3]
Preorder:   [1, 2, 4, 5, 3]
Postorder:  [4, 5, 2, 3, 1]
Level Order: [1, 2, 3, 4, 5]

---

Binary Tree Basics

Tree Node Definition

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

# Helper to build tree from list
def build_tree(values):
    """Build tree from level-order list (None represents null)"""
    if not values:
        return None
    
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    
    while queue and i < len(values):
        node = queue.pop(0)
        
        # Left child
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        
        # Right child
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    
    return root

# Example usage
root = build_tree([1, 2, 3, 4, 5])

Visual Representation

Complete tree representation with indices:

              1 (index 0)
             / \
            /   \
           /     \
          2       3 (indices 1, 2)
         / \     / \
        4   5   6   7 (indices 3, 4, 5, 6)
       / \
      8   9 (indices 7, 8)

Relationships:
- Parent of node i: (i - 1) // 2
- Left child of node i: 2*i + 1
- Right child of node i: 2*i + 2

---

Depth-First Search (DFS) Traversals

1. Inorder Traversal (Left → Root → Right)

Use case: Get values in sorted order for BST

Recursive Approach

def inorderTraversal(root: TreeNode) -> list[int]:
    """
    Inorder: Left → Root → Right
    
    Time: O(n) - visit each node once
    Space: O(h) - recursion stack, h = height
    """
    result = []
    
    def inorder(node):
        if not node:
            return
        
        inorder(node.left)       # Visit left subtree
        result.append(node.val)  # Visit root
        inorder(node.right)      # Visit right subtree
    
    inorder(root)
    return result

# Example
root = build_tree([1, None, 2, 3])
print(inorderTraversal(root))  # [1, 3, 2]

Execution trace:

Tree:    1
          \
           2
          /
         3

Call stack (going down):
inorder(1) → inorder(None) [left]
          → append 1
          → inorder(2) → inorder(3) → inorder(None) [left]
                                    → append 3
                                    → inorder(None) [right]
                      → append 2
                      → inorder(None) [right]

Result: [1, 3, 2]

Iterative Approach (Using Stack)

def inorderTraversal(root: TreeNode) -> list[int]:
    """
    Iterative inorder using explicit stack
    
    Time: O(n)
    Space: O(h)
    """
    result = []
    stack = []
    current = root
    
    while current or stack:
        # Go to leftmost node
        while current:
            stack.append(current)
            current = current.left
        
        # Current must be None, pop from stack
        current = stack.pop()
        result.append(current.val)
        
        # Visit right subtree
        current = current.right
    
    return result

Stack visualization:

Tree:      2
          / \
         1   3

Step-by-step:
Initial: current = 2, stack = []

Step 1: Push 2, move to left
        current = 1, stack = [2]

Step 2: Push 1, move to left
        current = None, stack = [2, 1]

Step 3: Pop 1, append 1
        current = None (1.right), stack = [2]
        Result: [1]

Step 4: Pop 2, append 2
        current = 3 (2.right), stack = []
        Result: [1, 2]

Step 5: Push 3, move to left
        current = None, stack = [3]

Step 6: Pop 3, append 3
        current = None, stack = []
        Result: [1, 2, 3]

---

2. Preorder Traversal (Root → Left → Right)

Use case: Copy tree, serialize tree

Recursive Approach

def preorderTraversal(root: TreeNode) -> list[int]:
    """
    Preorder: Root → Left → Right
    
    Time: O(n)
    Space: O(h)
    """
    result = []
    
    def preorder(node):
        if not node:
            return
        
        result.append(node.val)  # Visit root first
        preorder(node.left)      # Visit left subtree
        preorder(node.right)     # Visit right subtree
    
    preorder(root)
    return result

Iterative Approach

def preorderTraversal(root: TreeNode) -> list[int]:
    """
    Iterative preorder
    
    Strategy: Use stack, visit node before children
    """
    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

Visual execution:

Tree:      1
          / \
         2   3

Initial: stack = [1]

Step 1: Pop 1, append 1
        Push 3, 2
        stack = [3, 2], result = [1]

Step 2: Pop 2, append 2
        (2 has no children)
        stack = [3], result = [1, 2]

Step 3: Pop 3, append 3
        (3 has no children)
        stack = [], result = [1, 2, 3]

---

3. Postorder Traversal (Left → Right → Root)

Use case: Delete tree, evaluate expression tree

Recursive Approach

def postorderTraversal(root: TreeNode) -> list[int]:
    """
    Postorder: Left → Right → Root
    
    Time: O(n)
    Space: O(h)
    """
    result = []
    
    def postorder(node):
        if not node:
            return
        
        postorder(node.left)     # Visit left subtree
        postorder(node.right)    # Visit right subtree
        result.append(node.val)  # Visit root last
    
    postorder(root)
    return result

Iterative Approach (Two Stacks)

def postorderTraversal(root: TreeNode) -> list[int]:
    """
    Iterative postorder using two stacks
    
    Idea: Reverse of (Root → Right → Left) is (Left → Right → Root)
    """
    if not root:
        return []
    
    stack1 = [root]
    stack2 = []
    
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        
        # Push left first (so right is processed first)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    
    # stack2 now has postorder in reverse
    result = []
    while stack2:
        result.append(stack2.pop().val)
    
    return result

Iterative Approach (One Stack)

def postorderTraversal(root: TreeNode) -> list[int]:
    """
    Iterative postorder using one stack
    
    More complex: need to track visited nodes
    """
    if not root:
        return []
    
    result = []
    stack = [root]
    last_visited = None
    
    while stack:
        current = stack[-1]  # Peek
        
        # If leaf or both children visited, process node
        if (not current.left and not current.right) or \
           (last_visited and (last_visited == current.left or last_visited == current.right)):
            result.append(current.val)
            stack.pop()
            last_visited = current
        else:
            # Push children (right first, then left)
            if current.right:
                stack.append(current.right)
            if current.left:
                stack.append(current.left)
    
    return result

---

Breadth-First Search (BFS) Traversal

Level Order Traversal

Use case: Find shortest path, level-by-level processing

from collections import deque

def levelOrder(root: TreeNode) -> list[list[int]]:
    """
    Level order traversal (BFS)
    
    Returns list of lists, each inner list is one level
    
    Time: O(n)
    Space: O(w) where w is maximum width
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level = []
        
        # Process all nodes at current level
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            
            # Add children for next level
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

# Example
root = build_tree([3, 9, 20, None, None, 15, 7])
print(levelOrder(root))
# [[3], [9, 20], [15, 7]]

Visual execution:

Tree:        3
           /   \
          9     20
               /  \
              15   7

Initial: queue = [3], result = []

Level 0:
  queue = [3], level_size = 1
  Process 3: level = [3], queue = [9, 20]
  result = [[3]]

Level 1:
  queue = [9, 20], level_size = 2
  Process 9: level = [9], queue = [20]
  Process 20: level = [9, 20], queue = [15, 7]
  result = [[3], [9, 20]]

Level 2:
  queue = [15, 7], level_size = 2
  Process 15: level = [15], queue = [7]
  Process 7: level = [15, 7], queue = []
  result = [[3], [9, 20], [15, 7]]

---

Traversal Comparison

Visual Comparison

Tree:        1
           /   \
          2     3
         / \
        4   5

Inorder:    4  2  5  1  3  (Left → Root → Right)
                ↑     ↑  ↑
            Visits root in middle

Preorder:   1  2  4  5  3  (Root → Left → Right)
            ↑
            Visits root first

Postorder:  4  5  2  3  1  (Left → Right → Root)
                        ↑
            Visits root last

Level Order: 1  2  3  4  5 (Level by level)
             Level 0  Level 1  Level 2

When to Use Each

Traversal	Use Case	Example Application
Inorder	Process BST in sorted order	Validate BST, flatten to sorted list
Preorder	Create copy, serialize tree	Tree serialization, prefix expression
Postorder	Delete tree, calculate subtree properties	Delete tree, calculate height, postfix expression
Level Order	Find shortest path, level-wise processing	Print by levels, find min depth

---

Morris Traversal (O(1) Space)

Problem: All previous approaches use O(h) space. Can we do O(1)?

Answer: Yes! Morris traversal uses threaded binary tree concept.

Morris Inorder Traversal

def morrisInorder(root: TreeNode) -> list[int]:
    """
    Morris inorder traversal
    
    Time: O(n)
    Space: O(1) - no stack/recursion!
    
    Idea: Create temporary links (threads) to predecessor
    """
    result = []
    current = root
    
    while current:
        if not current.left:
            # No left subtree, visit current
            result.append(current.val)
            current = current.right
        else:
            # Find inorder predecessor (rightmost in left subtree)
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            
            if not predecessor.right:
                # Create thread
                predecessor.right = current
                current = current.left
            else:
                # Thread exists, remove it
                predecessor.right = None
                result.append(current.val)
                current = current.right
    
    return result

Visualization:

Original Tree:     Modified During Morris:

      1                  1
     / \                / \
    2   3              2   3
   / \                / \
  4   5              4   5
                          \
                           1 (thread)

Steps:
1. current = 1, find predecessor (5)
2. Create thread 5 → 1
3. Move to left subtree (current = 2)
4. Find predecessor (4) for 2
5. Create thread 4 → 2
... continue until all threads explored

Time complexity analysis:

• Each edge traversed at most twice (once to create thread, once to remove)
• Total: O(n)

---

Advanced Traversal Problems

Problem 1: Zigzag Level Order

def zigzagLevelOrder(root: TreeNode) -> list[list[int]]:
    """
    Level order but alternate direction
    
    Level 0: left to right
    Level 1: right to left
    Level 2: left to right
    ...
    
    Time: O(n), Space: O(w)
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    left_to_right = True
    
    while queue:
        level_size = len(queue)
        level = deque()
        
        for _ in range(level_size):
            node = queue.popleft()
            
            # Add to level based on direction
            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

# Example
root = build_tree([3, 9, 20, None, None, 15, 7])
print(zigzagLevelOrder(root))
# [[3], [20, 9], [15, 7]]

Problem 2: Vertical Order Traversal

from collections import defaultdict

def verticalOrder(root: TreeNode) -> list[list[int]]:
    """
    Traverse by vertical columns
    
    Assign column numbers:
    - Root at column 0
    - Left child: column - 1
    - Right child: column + 1
    
    Time: O(n log n), Space: O(n)
    """
    if not root:
        return []
    
    # Dictionary: column → list of (row, val)
    columns = defaultdict(list)
    
    # BFS with (node, row, col)
    queue = deque([(root, 0, 0)])
    
    while queue:
        node, row, col = queue.popleft()
        columns[col].append((row, node.val))
        
        if node.left:
            queue.append((node.left, row + 1, col - 1))
        if node.right:
            queue.append((node.right, row + 1, col + 1))
    
    # Sort columns by column index
    result = []
    for col in sorted(columns.keys()):
        # Sort by row, then by value
        column_vals = [val for row, val in sorted(columns[col])]
        result.append(column_vals)
    
    return result

# Example
#       1
#      / \
#     2   3
#    / \   \
#   4   5   6
#
# Columns: -2:[4], -1:[2], 0:[1,5], 1:[3], 2:[6]
# Result: [[4], [2], [1, 5], [3], [6]]

Problem 3: Boundary Traversal

def boundaryTraversal(root: TreeNode) -> list[int]:
    """
    Return boundary nodes in counter-clockwise order
    
    Boundary = left boundary + leaves + right boundary (reversed)
    
    Time: O(n), Space: O(h)
    """
    if not root:
        return []
    
    def is_leaf(node):
        return not node.left and not node.right
    
    def add_left_boundary(node, result):
        """Add left boundary (excluding leaves)"""
        while node:
            if not is_leaf(node):
                result.append(node.val)
            node = node.left if node.left else node.right
    
    def add_leaves(node, result):
        """Add all leaves"""
        if not node:
            return
        if is_leaf(node):
            result.append(node.val)
        add_leaves(node.left, result)
        add_leaves(node.right, result)
    
    def add_right_boundary(node, result):
        """Add right boundary (excluding leaves) in reverse"""
        temp = []
        while node:
            if not is_leaf(node):
                temp.append(node.val)
            node = node.right if node.right else node.left
        result.extend(reversed(temp))
    
    result = [root.val]
    if is_leaf(root):
        return result
    
    add_left_boundary(root.left, result)
    add_leaves(root.left, result)
    add_leaves(root.right, result)
    add_right_boundary(root.right, result)
    
    return result

Visualization:

Tree:          1
             /   \
            2     3
           / \     \
          4   5     6
         /         / \
        7         8   9

Boundary (counter-clockwise):
Left boundary:  1 → 2 → 4 → 7
Leaves:         7, 5, 8, 9
Right boundary: 6 → 3 → 1 (reversed)

Result: [1, 2, 4, 7, 5, 8, 9, 6, 3]

---

Connection to ML Systems

Tree traversal patterns appear in ML engineering:

1. Decision Tree Traversal

class DecisionTreeNode:
    def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):
        self.feature = feature      # Feature to split on
        self.threshold = threshold  # Threshold value
        self.left = left           # Left child
        self.right = right         # Right child
        self.value = value         # Leaf value

def predict_decision_tree(root: DecisionTreeNode, sample: dict) -> float:
    """
    Traverse decision tree to make prediction
    
    This is essentially a modified preorder traversal
    """
    if root.value is not None:
        # Leaf node
        return root.value
    
    # Internal node: check condition
    if sample[root.feature] <= root.threshold:
        return predict_decision_tree(root.left, sample)
    else:
        return predict_decision_tree(root.right, sample)

# Example
tree = DecisionTreeNode(
    feature='age',
    threshold=30,
    left=DecisionTreeNode(value=0),  # Predict 0 if age <= 30
    right=DecisionTreeNode(value=1)  # Predict 1 if age > 30
)

sample = {'age': 25, 'income': 50000}
prediction = predict_decision_tree(tree, sample)

2. Feature Engineering Pipeline (DAG Traversal)

class FeatureNode:
    """Node in feature engineering DAG"""
    def __init__(self, name, transform_fn, dependencies=None):
        self.name = name
        self.transform_fn = transform_fn
        self.dependencies = dependencies or []
        self.result = None

def topological_sort_features(nodes: list[FeatureNode]) -> list[FeatureNode]:
    """
    Topological sort of feature dependencies
    
    Similar to postorder: compute dependencies before current node
    """
    visited = set()
    result = []
    
    def dfs(node):
        if node.name in visited:
            return
        visited.add(node.name)
        
        # Visit dependencies first (like postorder)
        for dep in node.dependencies:
            dfs(dep)
        
        result.append(node)
    
    for node in nodes:
        dfs(node)
    
    return result

# Example
raw_age = FeatureNode('raw_age', lambda x: x['age'])
age_squared = FeatureNode('age_squared', lambda x: x['age'] ** 2, dependencies=[raw_age])
age_log = FeatureNode('age_log', lambda x: np.log(x['age']), dependencies=[raw_age])

features = topological_sort_features([age_log, age_squared, raw_age])
# Result: [raw_age, age_squared, age_log] or [raw_age, age_log, age_squared]

3. Model Ensembles (Tree of Models)

class EnsembleNode:
    """Node in ensemble hierarchy"""
    def __init__(self, model=None, left=None, right=None, combiner=None):
        self.model = model        # Base model
        self.left = left         # Left sub-ensemble
        self.right = right       # Right sub-ensemble
        self.combiner = combiner # How to combine predictions

def predict_ensemble(root: EnsembleNode, X):
    """
    Hierarchical ensemble prediction
    
    Uses postorder: get child predictions before combining
    """
    if root.model is not None:
        # Leaf: base model
        return root.model.predict(X)
    
    # Get predictions from sub-ensembles
    left_pred = predict_ensemble(root.left, X)
    right_pred = predict_ensemble(root.right, X)
    
    # Combine
    return root.combiner(left_pred, right_pred)

# Example: Ensemble of ensembles
def average(a, b):
    return (a + b) / 2

ensemble = EnsembleNode(
    combiner=average,
    left=EnsembleNode(model=model1),
    right=EnsembleNode(
        combiner=average,
        left=EnsembleNode(model=model2),
        right=EnsembleNode(model=model3)
    )
)

---

Testing

Comprehensive Test Suite

import unittest

class TestTreeTraversal(unittest.TestCase):
    
    def setUp(self):
        """Create test trees"""
        # Tree 1:     1
        #           /   \
        #          2     3
        self.tree1 = TreeNode(1)
        self.tree1.left = TreeNode(2)
        self.tree1.right = TreeNode(3)
        
        # Tree 2:     1
        #           /   \
        #          2     3
        #         / \
        #        4   5
        self.tree2 = build_tree([1, 2, 3, 4, 5])
    
    def test_inorder(self):
        """Test inorder traversal"""
        self.assertEqual(inorderTraversal(self.tree1), [2, 1, 3])
        self.assertEqual(inorderTraversal(self.tree2), [4, 2, 5, 1, 3])
    
    def test_preorder(self):
        """Test preorder traversal"""
        self.assertEqual(preorderTraversal(self.tree1), [1, 2, 3])
        self.assertEqual(preorderTraversal(self.tree2), [1, 2, 4, 5, 3])
    
    def test_postorder(self):
        """Test postorder traversal"""
        self.assertEqual(postorderTraversal(self.tree1), [2, 3, 1])
        self.assertEqual(postorderTraversal(self.tree2), [4, 5, 2, 3, 1])
    
    def test_level_order(self):
        """Test level order traversal"""
        self.assertEqual(levelOrder(self.tree1), [[1], [2, 3]])
        self.assertEqual(levelOrder(self.tree2), [[1], [2, 3], [4, 5]])
    
    def test_empty_tree(self):
        """Test empty tree"""
        self.assertEqual(inorderTraversal(None), [])
        self.assertEqual(levelOrder(None), [])
    
    def test_single_node(self):
        """Test single node"""
        single = TreeNode(1)
        self.assertEqual(inorderTraversal(single), [1])
        self.assertEqual(preorderTraversal(single), [1])
        self.assertEqual(postorderTraversal(single), [1])

if __name__ == '__main__':
    unittest.main()

---

Interview Tips

Pattern Recognition

When you see:

• “Process tree nodes in specific order”
• “Find path from root to node”
• “Compute tree property”
• “Level-wise processing”

Think: Tree traversal

Choosing the Right Traversal

Decision tree:

Need specific order? ────────────────────────┐
│                                            │
├─ Sorted (BST): Inorder                    │
├─ Copy/Serialize: Preorder                 │
├─ Delete/Calculate: Postorder              │
└─ Level-wise: BFS                          │
                                             │
Space constraint? ───────────────────────────┤
│                                            │
├─ O(1) space needed: Morris                │
└─ O(h) acceptable: Recursive/Iterative     │

Common Mistakes

1. Forgetting base case:

# WRONG
def inorder(node):
    inorder(node.left)  # Crashes on None!
    print(node.val)
    inorder(node.right)

# CORRECT
def inorder(node):
    if not node:
        return
    inorder(node.left)
    print(node.val)
    inorder(node.right)

2. Modifying tree during traversal:

# DANGEROUS: Modifying tree structure
def dangerous_traversal(node):
    if not node:
        return
    dangerous_traversal(node.left)
    node.left = None  # Oops! Can cause issues
    dangerous_traversal(node.right)

3. Not considering empty tree:

# WRONG
def get_height(root):
    return 1 + max(get_height(root.left), get_height(root.right))
    # Crashes if root is None!

# CORRECT
def get_height(root):
    if not root:
        return 0
    return 1 + max(get_height(root.left), get_height(root.right))

---

Performance Analysis & Optimization

Space Complexity Deep Dive

Traversal Method        Space Complexity    Notes
─────────────────────────────────────────────────────────────
Recursive DFS           O(h)               Recursion stack
Iterative DFS (stack)   O(h)               Explicit stack
BFS (queue)             O(w)               w = max width
Morris Traversal        O(1)               No extra space!

For balanced tree:      h = log n
For skewed tree:        h = n (worst case)
For complete tree:      w = n/2 (last level)

Performance Comparison

import time
import sys

def measure_traversal_performance(tree_size=10000):
    """
    Benchmark different traversal methods
    """
    # Create balanced tree
    root = create_balanced_tree(tree_size)
    
    methods = [
        ('Recursive Inorder', lambda: inorderTraversal(root)),
        ('Iterative Inorder', lambda: inorderTraversalIterative(root)),
        ('Morris Inorder', lambda: morrisInorder(root)),
        ('Level Order BFS', lambda: levelOrder(root))
    ]
    
    results = []
    
    for name, method in methods:
        # Measure time
        start = time.perf_counter()
        result = method()
        end = time.perf_counter()
        
        # Measure space (approximate)
        # This is simplified; real measurement would be more complex
        
        results.append({
            'method': name,
            'time_ms': (end - start) * 1000,
            'result_length': len(result)
        })
    
    return results

def create_balanced_tree(n):
    """Create balanced tree with n nodes"""
    if n == 0:
        return None
    
    values = list(range(1, n + 1))
    
    def build(start, end):
        if start > end:
            return None
        
        mid = (start + end) // 2
        node = TreeNode(values[mid])
        node.left = build(start, mid - 1)
        node.right = build(mid + 1, end)
        return node
    
    return build(0, n - 1)

# Benchmark
results = measure_traversal_performance(10000)
for r in results:
    print(f"{r['method']:25s}: {r['time_ms']:.2f}ms")

Typical results (10,000 nodes):

Recursive Inorder        : 8.23ms
Iterative Inorder        : 9.15ms  (slightly slower due to stack operations)
Morris Inorder           : 12.47ms (slower but O(1) space!)
Level Order BFS          : 10.33ms

---

Edge Cases & Corner Cases

1. Empty Tree

def handle_empty_tree():
    """All traversals should handle None gracefully"""
    empty_root = None
    
    assert inorderTraversal(empty_root) == []
    assert preorderTraversal(empty_root) == []
    assert postorderTraversal(empty_root) == []
    assert levelOrder(empty_root) == []
    
    print("✓ Empty tree handled correctly")

2. Single Node

def handle_single_node():
    """Single node is both root and leaf"""
    single = TreeNode(42)
    
    assert inorderTraversal(single) == [42]
    assert preorderTraversal(single) == [42]
    assert postorderTraversal(single) == [42]
    assert levelOrder(single) == [[42]]
    
    print("✓ Single node handled correctly")

3. Skewed Tree (Linked List)

def create_right_skewed_tree(n):
    """
    Create right-skewed tree (like linked list)
    
         1
          \
           2
            \
             3
              \
               4
    
    Worst case for space complexity: O(n)
    """
    if n == 0:
        return None
    
    root = TreeNode(1)
    current = root
    
    for i in range(2, n + 1):
        current.right = TreeNode(i)
        current = current.right
    
    return root

# Test skewed tree
skewed = create_right_skewed_tree(5)
assert inorderTraversal(skewed) == [1, 2, 3, 4, 5]
assert preorderTraversal(skewed) == [1, 2, 3, 4, 5]
assert postorderTraversal(skewed) == [5, 4, 3, 2, 1]

4. Large Values & Overflow

def handle_large_values():
    """Test with large integers"""
    tree = TreeNode(2**31 - 1)  # Max int
    tree.left = TreeNode(-(2**31))  # Min int
    tree.right = TreeNode(0)
    
    result = inorderTraversal(tree)
    assert result == [-(2**31), 2**31 - 1, 0]
    
    print("✓ Large values handled correctly")

---

Advanced Applications

1. Expression Tree Evaluation

class ExpressionNode:
    """Node for expression tree"""
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def evaluate_expression_tree(root: ExpressionNode) -> float:
    """
    Evaluate arithmetic expression tree
    
    Uses postorder: evaluate children before parent
    
    Example tree:
            +
           / \
          *   3
         / \
        5   4
    
    Result: (5 * 4) + 3 = 23
    """
    if not root:
        return 0
    
    # Leaf node: return value
    if not root.left and not root.right:
        return float(root.val)
    
    # Evaluate subtrees (postorder)
    left_val = evaluate_expression_tree(root.left)
    right_val = evaluate_expression_tree(root.right)
    
    # Apply operator
    if root.val == '+':
        return left_val + right_val
    elif root.val == '-':
        return left_val - right_val
    elif root.val == '*':
        return left_val * right_val
    elif root.val == '/':
        return left_val / right_val
    else:
        return float(root.val)

# Example: (5 * 4) + 3
expr_tree = ExpressionNode(
    '+',
    left=ExpressionNode(
        '*',
        left=ExpressionNode('5'),
        right=ExpressionNode('4')
    ),
    right=ExpressionNode('3')
)

result = evaluate_expression_tree(expr_tree)
print(f"Expression result: {result}")  # 23.0

2. Serialize/Deserialize Tree

def serialize(root: TreeNode) -> str:
    """
    Serialize tree to string (preorder)
    
    Example:
         1
        / \
       2   3
          / \
         4   5
    
    Serialized: "1,2,None,None,3,4,None,None,5,None,None"
    """
    def preorder(node):
        if not node:
            return ['None']
        
        return [str(node.val)] + preorder(node.left) + preorder(node.right)
    
    return ','.join(preorder(root))

def deserialize(data: str) -> TreeNode:
    """
    Deserialize string to tree
    
    Uses preorder reconstruction
    """
    def build_tree(values):
        val = next(values)
        
        if val == 'None':
            return None
        
        node = TreeNode(int(val))
        node.left = build_tree(values)
        node.right = build_tree(values)
        
        return node
    
    values = iter(data.split(','))
    return build_tree(values)

# Example
original = build_tree([1, 2, 3, 4, 5])
serialized = serialize(original)
print(f"Serialized: {serialized}")

deserialized = deserialize(serialized)
assert inorderTraversal(deserialized) == inorderTraversal(original)
print("✓ Serialize/Deserialize works correctly")

3. Find Lowest Common Ancestor

def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    """
    Find lowest common ancestor of two nodes
    
    Uses postorder: need information from subtrees
    
    Time: O(n), Space: O(h)
    """
    # Base cases
    if not root or root == p or root == q:
        return root
    
    # Search in subtrees
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    # If p and q are in different subtrees, current node is LCA
    if left and right:
        return root
    
    # Otherwise, return non-null result
    return left if left else right

# Example
#       3
#      / \
#     5   1
#    / \
#   6   2
tree = TreeNode(3)
tree.left = TreeNode(5)
tree.right = TreeNode(1)
tree.left.left = TreeNode(6)
tree.left.right = TreeNode(2)

lca = lowestCommonAncestor(tree, tree.left, tree.left.right)
print(f"LCA of 5 and 2: {lca.val}")  # 5

4. Tree Diameter

def diameter_of_tree(root: TreeNode) -> int:
    """
    Find diameter (longest path between any two nodes)
    
    Uses postorder: compute height of subtrees
    
    Time: O(n), Space: O(h)
    """
    max_diameter = [0]  # Use list to modify in nested function
    
    def height(node):
        if not node:
            return 0
        
        # Get heights of subtrees
        left_height = height(node.left)
        right_height = height(node.right)
        
        # Update diameter (path through this node)
        diameter_through_node = left_height + right_height
        max_diameter[0] = max(max_diameter[0], diameter_through_node)
        
        # Return height of this subtree
        return 1 + max(left_height, right_height)
    
    height(root)
    return max_diameter[0]

# Example
#       1
#      / \
#     2   3
#    / \
#   4   5
tree = build_tree([1, 2, 3, 4, 5])
diameter = diameter_of_tree(tree)
print(f"Diameter: {diameter}")  # 3 (path: 4 → 2 → 1 → 3)

---

Production Considerations

1. Concurrent Tree Traversal

from threading import Lock
from collections import deque

class ThreadSafeTree:
    """
    Thread-safe tree operations
    
    Important for production systems with concurrent reads/writes
    """
    
    def __init__(self, root):
        self.root = root
        self.lock = Lock()
    
    def inorder_snapshot(self):
        """
        Get inorder traversal snapshot atomically
        """
        with self.lock:
            return inorderTraversal(self.root)
    
    def insert(self, val):
        """Thread-safe insertion"""
        with self.lock:
            self._insert_helper(self.root, val)
    
    def _insert_helper(self, node, val):
        """Insert into BST"""
        if not node:
            return TreeNode(val)
        
        if val < node.val:
            node.left = self._insert_helper(node.left, val)
        else:
            node.right = self._insert_helper(node.right, val)
        
        return node

2. Lazy Evaluation for Large Trees

def lazy_inorder_generator(root):
    """
    Generator for lazy inorder traversal
    
    Yields nodes one at a time (memory efficient)
    """
    if not root:
        return
    
    # Use generator for left subtree
    yield from lazy_inorder_generator(root.left)
    
    # Yield current
    yield root.val
    
    # Use generator for right subtree
    yield from lazy_inorder_generator(root.right)

# Usage: process large tree without loading all values
for val in lazy_inorder_generator(root):
    if val > 100:  # Can stop early
        break
    process(val)

3. Monitoring & Logging

class InstrumentedTraversal:
    """
    Traversal with monitoring
    
    Track performance metrics for production debugging
    """
    
    def __init__(self):
        self.nodes_visited = 0
        self.max_depth_reached = 0
        self.start_time = None
        self.end_time = None
    
    def inorder_with_metrics(self, root, current_depth=0):
        """Inorder with metrics collection"""
        if self.start_time is None:
            self.start_time = time.time()
        
        if not root:
            return []
        
        self.nodes_visited += 1
        self.max_depth_reached = max(self.max_depth_reached, current_depth)
        
        result = []
        result.extend(self.inorder_with_metrics(root.left, current_depth + 1))
        result.append(root.val)
        result.extend(self.inorder_with_metrics(root.right, current_depth + 1))
        
        if current_depth == 0:  # Back at root
            self.end_time = time.time()
        
        return result
    
    def get_metrics(self):
        """Get traversal metrics"""
        return {
            'nodes_visited': self.nodes_visited,
            'max_depth': self.max_depth_reached,
            'time_ms': (self.end_time - self.start_time) * 1000 if self.end_time else 0
        }

# Usage
instrumented = InstrumentedTraversal()
result = instrumented.inorder_with_metrics(root)
metrics = instrumented.get_metrics()
print(f"Metrics: {metrics}")

---

Interview Strategy

Step-by-Step Approach

1. Clarify (1-2 min):

• What traversal order is needed?
• Return list or perform action at each node?
• Any constraints on space?
• Can the tree be modified?

2. State Approach (1 min):

• “I’ll use [inorder/preorder/postorder/level-order] because…”
• “For this problem, I’ll go with [recursive/iterative] approach”

3. Code (5-8 min):

• Start with base case
• Implement traversal logic
• Test with example

4. Test (2-3 min):

• Empty tree
• Single node
• Balanced tree
• Skewed tree

5. Optimize (2 min):

• Discuss Morris if O(1) space needed
• Discuss iterative if recursion limit is concern

Common Follow-Up Questions

Q: Can you do this without recursion?

# Show iterative approach with stack

Q: Can you do this in O(1) space?

# Show Morris traversal

Q: What if the tree is very large (doesn’t fit in memory)?

# Discuss lazy evaluation, generators, streaming

Q: How would you parallelize this?

# Discuss level-order parallelization:
# Process each level in parallel
def parallel_level_order(root):
    if not root:
        return []
    
    from concurrent.futures import ThreadPoolExecutor
    
    result = []
    current_level = [root]
    
    while current_level:
        # Process level in parallel
        with ThreadPoolExecutor() as executor:
            values = list(executor.map(lambda n: n.val, current_level))
        result.append(values)
        
        # Get next level
        next_level = []
        for node in current_level:
            if node.left:
                next_level.append(node.left)
            if node.right:
                next_level.append(node.right)
        
        current_level = next_level
    
    return result

---

Key Takeaways

✅ Three DFS orders - Inorder (sorted for BST), Preorder (copy), Postorder (delete)
✅ BFS for levels - Use queue for level-order traversal
✅ Recursion naturally fits trees - Base case is null node
✅ Stack for iterative DFS - Simulate recursion call stack
✅ Morris for O(1) space - Use threaded links, restore tree after
✅ Choose traversal by use case - Different problems need different orders
✅ ML applications - Decision trees, feature DAGs, ensemble hierarchies

---

Related Problems

Master these to solidify tree traversal:

• Binary Tree Level Order Traversal - BFS basics
• Binary Tree Zigzag Level Order - BFS variation
• Validate Binary Search Tree - Inorder application
• Serialize and Deserialize Binary Tree - Preorder application
• Binary Tree Maximum Path Sum - Postorder application
• Vertical Order Traversal - Custom traversal

---

Originally published at: arunbaby.com/dsa/0007-binary-tree-traversal

If you found this helpful, consider sharing it with others who might benefit.