Binary Tree Traversal

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

TL;DR

Four traversal orders, each with a specific use: inorder (left-root-right) gives sorted BST output, preorder (root-left-right) serializes trees, postorder (left-right-root) computes subtree properties, and level-order (BFS with queue) processes by depth. All run in O(n) time. Recursive and iterative (stack-based) approaches use O(h) space; Morris traversal achieves O(1) by threading temporary links. These traversals are the building blocks for BST validation (inorder must be sorted) and connect to the stack patterns from Valid Parentheses.

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

---

FAQ

Q: What are the four types of binary tree traversal? A: Inorder visits left-root-right (produces sorted order for BSTs), preorder visits root-left-right (used for tree copying and serialization), postorder visits left-right-root (used for deletion and expression evaluation), and level-order visits nodes level by level using BFS with a queue.

Q: What is the time and space complexity of tree traversal? A: All traversals visit each node exactly once, giving O(n) time. Recursive DFS and iterative DFS both use O(h) space where h is the tree height (O(log n) for balanced, O(n) for skewed). Level-order BFS uses O(w) space where w is the maximum width. Morris traversal achieves O(1) space.

Q: How does Morris traversal achieve O(1) space? A: Morris traversal creates temporary threaded links from inorder predecessors back to their successors, eliminating the need for a stack or recursion. When it encounters a thread during traversal, it removes it and visits the node. Each edge is traversed at most twice, maintaining O(n) time.

Q: When should I use each traversal order? A: Use inorder for BST operations (validation, kth smallest), preorder for serialization and tree copying, postorder for computing subtree properties (height, size, deletion), and level-order for shortest-path problems and level-wise processing like zigzag traversal.

Q: How do tree traversals apply to ML systems? A: Decision tree inference uses preorder traversal following split conditions to leaves. Feature engineering DAGs use topological sort (postorder variant) to resolve dependencies. Hierarchical model ensembles use postorder to combine child predictions before parent aggregation.

---

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

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