Topic Overview

Tree Traversal

Master tree traversal algorithms: preorder, inorder, postorder, and level-order traversal for binary trees and n-ary trees.

Tree traversal is the process of visiting all nodes in a tree in a systematic way. Understanding different traversal orders is essential for solving tree-based problems.

Why This Matters in Interviews

Tree traversal is fundamental because:

  • Tree problems: Most tree problems require traversal
  • Algorithm foundation: Basis for many tree algorithms
  • Problem patterns: Different traversals solve different problems
  • Implementation skills: Tests recursive and iterative thinking

Interviewers use tree traversal to assess your understanding of trees, recursion, and your ability to choose the right traversal for a problem.

Core Concepts

  • Preorder: Root → Left → Right
  • Inorder: Left → Root → Right (gives sorted order for BST)
  • Postorder: Left → Right → Root
  • Level-order: Breadth-first, level by level
  • DFS vs BFS: Depth-first (stack) vs breadth-first (queue)
  • Iterative vs recursive: Both implementations important
  • Morris traversal: Inorder without stack/recursion

Detailed Explanation

Tree Node Structure

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

Preorder Traversal

Recursive:

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

// Order: Root → Left → Right

Iterative:

function preorderIterative(root: TreeNode | null): number[] {
  if (!root) return [];
  
  const result: number[] = [];
  const stack: TreeNode[] = [root];
  
  while (stack.length > 0) {
    const node = stack.pop()!;
    result.push(node.val);
    
    // Push right first, then left (stack is LIFO)
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  
  return result;
}

// Time: O(n), Space: O(h) where h is height

Inorder Traversal

Recursive:

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

// Order: Left → Root → Right
// For BST: Gives sorted order

Iterative:

function inorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  const stack: TreeNode[] = [];
  let current: TreeNode | null = root;
  
  while (current || stack.length > 0) {
    // Go to leftmost node
    while (current) {
      stack.push(current);
      current = current.left;
    }
    
    // Process node
    current = stack.pop()!;
    result.push(current.val);
    
    // Move to right subtree
    current = current.right;
  }
  
  return result;
}

// Time: O(n), Space: O(h)

Postorder Traversal

Recursive:

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

// Order: Left → Right → Root

Iterative:

function postorderIterative(root: TreeNode | null): number[] {
  if (!root) return [];
  
  const result: number[] = [];
  const stack: TreeNode[] = [root];
  const visited = new Set<TreeNode>();
  
  while (stack.length > 0) {
    const node = stack[stack.length - 1];
    
    // If both children processed or leaf node
    if ((!node.left && !node.right) || 
        (node.right && visited.has(node.right)) ||
        (!node.right && node.left && visited.has(node.left))) {
      result.push(node.val);
      visited.add(node);
      stack.pop();
    } else {
      // Push children (right first, then left)
      if (node.right && !visited.has(node.right)) {
        stack.push(node.right);
      }
      if (node.left && !visited.has(node.left)) {
        stack.push(node.left);
      }
    }
  }
  
  return result;
}

// Time: O(n), Space: O(h)

Level-Order Traversal (BFS)

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 level: number[] = [];
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      level.push(node.val);
      
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    
    result.push(level);
  }
  
  return result;
}

// Time: O(n), Space: O(w) where w is max width

Morris Inorder Traversal (O(1) Space)

function morrisInorder(root: TreeNode | null): number[] {
  const result: number[] = [];
  let current: TreeNode | null = root;
  
  while (current) {
    if (!current.left) {
      // No left subtree, visit and go right
      result.push(current.val);
      current = current.right;
    } else {
      // Find inorder predecessor
      let predecessor = current.left;
      while (predecessor.right && predecessor.right !== current) {
        predecessor = predecessor.right;
      }
      
      if (!predecessor.right) {
        // Make current right child of predecessor
        predecessor.right = current;
        current = current.left;
      } else {
        // Restore tree, visit current
        predecessor.right = null;
        result.push(current.val);
        current = current.right;
      }
    }
  }
  
  return result;
}

// Time: O(n), Space: O(1) - no stack/recursion!

Examples

N-ary Tree Traversal

class NaryNode {
  val: number;
  children: NaryNode[];
  
  constructor(val: number) {
    this.val = val;
    this.children = [];
  }
}

function preorderNary(root: NaryNode | null): number[] {
  const result: number[] = [];
  
  function traverse(node: NaryNode | null): void {
    if (!node) return;
    
    result.push(node.val);
    for (const child of node.children) {
      traverse(child);
    }
  }
  
  traverse(root);
  return result;
}

function levelOrderNary(root: NaryNode | null): number[][] {
  if (!root) return [];
  
  const result: number[][] = [];
  const queue: NaryNode[] = [root];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    const level: number[] = [];
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      level.push(node.val);
      
      for (const child of node.children) {
        queue.push(child);
      }
    }
    
    result.push(level);
  }
  
  return result;
}

Serialize/Deserialize Binary Tree

function serialize(root: TreeNode | null): string {
  const result: string[] = [];
  
  function preorder(node: TreeNode | null): void {
    if (!node) {
      result.push('null');
      return;
    }
    
    result.push(node.val.toString());
    preorder(node.left);
    preorder(node.right);
  }
  
  preorder(root);
  return result.join(',');
}

function deserialize(data: string): TreeNode | null {
  const values = data.split(',');
  let index = 0;
  
  function build(): TreeNode | null {
    if (values[index] === 'null') {
      index++;
      return null;
    }
    
    const node = new TreeNode(parseInt(values[index++]));
    node.left = build();
    node.right = build();
    return node;
  }
  
  return build();
}

Common Pitfalls

  • Null pointer errors: Not checking for null nodes. Fix: Always check before accessing
  • Stack overflow: Deep recursion on unbalanced trees. Fix: Use iterative or limit depth
  • Wrong order: Confusing traversal orders. Fix: Remember: pre=root first, in=middle, post=root last
  • Modifying tree during traversal: Can break traversal. Fix: Complete traversal before modifying
  • Space complexity: Forgetting stack/queue space. Fix: Consider O(h) for DFS, O(w) for BFS

Interview Questions

Beginner

Q: Explain the three main DFS traversal orders for binary trees. What is the order of node visits?

A:

Three DFS Traversal Orders:

1. Preorder (Root → Left → Right):

Visit root first, then left subtree, then right subtree

2. Inorder (Left → Root → Right):

Visit left subtree, then root, then right subtree
For BST: Gives sorted order

3. Postorder (Left → Right → Root):

Visit left subtree, then right subtree, then root
Useful for: Deleting tree, evaluating expressions

Example Tree:

      1
     / \
    2   3
   / \
  4   5

Traversals:

  • Preorder: 1, 2, 4, 5, 3
  • Inorder: 4, 2, 5, 1, 3
  • Postorder: 4, 5, 2, 3, 1

Key points:

  • Preorder: Root first
  • Inorder: Root middle (sorted for BST)
  • Postorder: Root last

Intermediate

Q: Implement iterative versions of all three DFS traversals. How do you handle the stack differently for each?

A:

Preorder (Simplest):

function preorderIterative(root: TreeNode | null): number[] {
  if (!root) return [];
  
  const result: number[] = [];
  const stack: TreeNode[] = [root];
  
  while (stack.length > 0) {
    const node = stack.pop()!;
    result.push(node.val);
    
    // Push right first (stack is LIFO)
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  
  return result;
}

Inorder (More complex):

function inorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  const stack: TreeNode[] = [];
  let current: TreeNode | null = root;
  
  while (current || stack.length > 0) {
    // Go to leftmost
    while (current) {
      stack.push(current);
      current = current.left;
    }
    
    // Process and go right
    current = stack.pop()!;
    result.push(current.val);
    current = current.right;
  }
  
  return result;
}

Postorder (Most complex):

function postorderIterative(root: TreeNode | null): number[] {
  if (!root) return [];
  
  const result: number[] = [];
  const stack: TreeNode[] = [root];
  const visited = new Set<TreeNode>();
  
  while (stack.length > 0) {
    const node = stack[stack.length - 1];
    
    // Check if ready to process
    const leftDone = !node.left || visited.has(node.left);
    const rightDone = !node.right || visited.has(node.right);
    
    if (leftDone && rightDone) {
      result.push(node.val);
      visited.add(node);
      stack.pop();
    } else {
      // Push children
      if (node.right && !visited.has(node.right)) {
        stack.push(node.right);
      }
      if (node.left && !visited.has(node.left)) {
        stack.push(node.left);
      }
    }
  }
  
  return result;
}

Key differences:

  • Preorder: Process immediately, push children
  • Inorder: Push all left, process, then right
  • Postorder: Need to track which children processed

Senior

Q: Design a tree traversal system that supports pausing, resuming, and iterating over a large tree that doesn't fit in memory. How do you handle state management and ensure efficient traversal?

A:

class TreeIterator {
  private stack: TreeNode[] = [];
  private current: TreeNode | null = null;
  private traversalType: 'preorder' | 'inorder' | 'postorder';
  private state: 'paused' | 'running' = 'running';
  
  constructor(root: TreeNode | null, type: 'preorder' | 'inorder' | 'postorder') {
    this.traversalType = type;
    this.initialize(root);
  }
  
  private initialize(root: TreeNode | null): void {
    if (!root) return;
    
    switch (this.traversalType) {
      case 'preorder':
        this.stack = [root];
        break;
      case 'inorder':
        this.current = root;
        this.pushLeft(root);
        break;
      case 'postorder':
        this.initializePostorder(root);
        break;
    }
  }
  
  private pushLeft(node: TreeNode | null): void {
    while (node) {
      this.stack.push(node);
      node = node.left;
    }
  }
  
  hasNext(): boolean {
    return this.stack.length > 0 || this.current !== null;
  }
  
  next(): number | null {
    if (this.state === 'paused') {
      throw new Error('Iterator is paused');
    }
    
    if (!this.hasNext()) {
      return null;
    }
    
    switch (this.traversalType) {
      case 'preorder':
        return this.nextPreorder();
      case 'inorder':
        return this.nextInorder();
      case 'postorder':
        return this.nextPostorder();
    }
  }
  
  private nextPreorder(): number {
    const node = this.stack.pop()!;
    if (node.right) this.stack.push(node.right);
    if (node.left) this.stack.push(node.left);
    return node.val;
  }
  
  private nextInorder(): number {
    while (this.current) {
      this.stack.push(this.current);
      this.current = this.current.left;
    }
    
    this.current = this.stack.pop()!;
    const val = this.current.val;
    this.current = this.current.right;
    return val;
  }
  
  private nextPostorder(): number {
    // Implementation similar to iterative postorder
    // ...
    return 0;
  }
  
  pause(): void {
    this.state = 'paused';
  }
  
  resume(): void {
    this.state = 'running';
  }
  
  // Save state for resuming later
  saveState(): IteratorState {
    return {
      stack: this.stack.map(n => this.serializeNode(n)),
      current: this.current ? this.serializeNode(this.current) : null,
      traversalType: this.traversalType
    };
  }
  
  restoreState(state: IteratorState): void {
    // Restore from saved state
    // Deserialize nodes as needed
  }
  
  private serializeNode(node: TreeNode): string {
    // Serialize node reference (e.g., path from root)
    return JSON.stringify({ val: node.val, path: this.getPath(node) });
  }
  
  private getPath(node: TreeNode): string {
    // Get path from root to node
    return '';
  }
}

// For very large trees: Stream-based traversal
class StreamingTreeTraversal {
  async *traverse(root: TreeNode | null): AsyncGenerator<number> {
    if (!root) return;
    
    const stack: TreeNode[] = [root];
    
    while (stack.length > 0) {
      const node = stack.pop()!;
      
      // Yield value (can be processed/streamed)
      yield node.val;
      
      // Process in chunks to avoid memory issues
      if (stack.length > 10000) {
        await this.processChunk(stack);
      }
      
      if (node.right) stack.push(node.right);
      if (node.left) stack.push(node.left);
    }
  }
  
  private async processChunk(stack: TreeNode[]): Promise<void> {
    // Process or persist chunk
    // Could write to disk, send over network, etc.
  }
}

// Usage
async function processLargeTree(root: TreeNode) {
  const traversal = new StreamingTreeTraversal();
  
  for await (const value of traversal.traverse(root)) {
    // Process each value as it's yielded
    processValue(value);
  }
}

Features:

  1. Iterator pattern: Lazy evaluation, one node at a time
  2. State management: Save/restore traversal state
  3. Pause/resume: Control traversal execution
  4. Streaming: For very large trees, process incrementally
  5. Memory efficient: Only stores path, not entire tree

Key Takeaways

  • Preorder: Root first, useful for copying trees, prefix expressions
  • Inorder: Root middle, gives sorted order for BST
  • Postorder: Root last, useful for deleting trees, postfix expressions
  • Level-order: BFS, processes level by level
  • Iterative vs recursive: Iterative uses explicit stack/queue
  • Space complexity: O(h) for DFS, O(w) for BFS
  • Morris traversal: O(1) space for inorder using tree structure

About the author

InterviewCrafted helps you master system design with patience. We believe in curiosity-led engineering, reflective writing, and designing systems that make future changes feel calm.