Binary Tree Traversal Algorithms Explained

Binary Tree Basics

A binary tree is an important data structure where each node has at most two children.

Node Definition

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

Depth-First Search (DFS)

1. Pre-order Traversal

Visit order: Root → Left subtree → Right subtree

Recursive Implementation

function preorderTraversal(root) {
  const result = [];

  function traverse(node) {
    if (!node) return;

    result.push(node.val); // Visit root node
    traverse(node.left); // Traverse left subtree
    traverse(node.right); // Traverse right subtree
  }

  traverse(root);
  return result;
}

Iterative Implementation

Using a stack to simulate the recursive process:

function preorderTraversal(root) {
  if (!root) return [];

  const result = [];
  const stack = [root];

  while (stack.length > 0) {
    const node = stack.pop();
    result.push(node.val);

    // Push right first, then left (because stack is LIFO)
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }

  return result;
}

2. In-order Traversal

Visit order: Left subtree → Root → Right subtree

For binary search trees, in-order traversal results in ascending order.

Recursive Implementation

function inorderTraversal(root) {
  const result = [];

  function traverse(node) {
    if (!node) return;

    traverse(node.left); // Traverse left subtree
    result.push(node.val); // Visit root node
    traverse(node.right); // Traverse right subtree
  }

  traverse(root);
  return result;
}

Iterative Implementation

function inorderTraversal(root) {
  const result = [];
  const stack = [];
  let current = root;

  while (current || stack.length > 0) {
    // Go left until we reach the end
    while (current) {
      stack.push(current);
      current = current.left;
    }

    // Pop and visit node
    current = stack.pop();
    result.push(current.val);

    // Move to right subtree
    current = current.right;
  }

  return result;
}

3. Post-order Traversal

Visit order: Left subtree → Right subtree → Root

Recursive Implementation

function postorderTraversal(root) {
  const result = [];

  function traverse(node) {
    if (!node) return;

    traverse(node.left); // Traverse left subtree
    traverse(node.right); // Traverse right subtree
    result.push(node.val); // Visit root node
  }

  traverse(root);
  return result;
}

Iterative Implementation

function postorderTraversal(root) {
  if (!root) return [];

  const result = [];
  const stack = [root];

  while (stack.length > 0) {
    const node = stack.pop();
    result.unshift(node.val); // Insert at the beginning of result array

    // Left first, then right
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }

  return result;
}

Breadth-First Search (BFS)

Level-order Traversal

Visit nodes level by level, implemented using a queue.

function levelOrder(root) {
  if (!root) return [];

  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.val);

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(currentLevel);
  }

  return result;
}

Zigzag Level-order Traversal

function zigzagLevelOrder(root) {
  if (!root) return [];

  const result = [];
  const queue = [root];
  let leftToRight = true;

  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();

      if (leftToRight) {
        currentLevel.push(node.val);
      } else {
        currentLevel.unshift(node.val);
      }

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(currentLevel);
    leftToRight = !leftToRight;
  }

  return result;
}

Practical Applications

1. Maximum Depth of Binary Tree

function maxDepth(root) {
  if (!root) return 0;

  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

2. Check if Balanced Binary Tree

function isBalanced(root) {
  function height(node) {
    if (!node) return 0;

    const leftHeight = height(node.left);
    if (leftHeight === -1) return -1;

    const rightHeight = height(node.right);
    if (rightHeight === -1) return -1;

    if (Math.abs(leftHeight - rightHeight) > 1) {
      return -1;
    }

    return Math.max(leftHeight, rightHeight) + 1;
  }

  return height(root) !== -1;
}

3. Lowest Common Ancestor of Binary Tree

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) {
    return root;
  }

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left && right) return root;
  return left || right;
}

Time and Space Complexity

Traversal Method	Time Complexity	Space Complexity (Worst)
Pre-order	O(n)	O(n)
In-order	O(n)	O(n)
Post-order	O(n)	O(n)
Level-order	O(n)	O(n)

Interview Tips

1. Recursive vs Iterative: Recursive code is more concise but may cause stack overflow; iterative uses explicit stack and is better for large datasets
2. Space Optimization: Morris traversal can achieve O(1) space complexity
3. Edge Cases: Pay attention to null node handling
4. Flexible Application: Many tree problems can be converted to traversal problems

Summary

Binary tree traversal is a fundamental yet important algorithm. Mastering both recursive and iterative implementations, understanding the application scenarios of DFS and BFS, is crucial for solving complex tree problems.

Recommended Practice Problems

• LeetCode 94: Binary Tree Inorder Traversal
• LeetCode 102: Binary Tree Level Order Traversal
• LeetCode 144: Binary Tree Preorder Traversal
• LeetCode 145: Binary Tree Postorder Traversal
• LeetCode 103: Binary Tree Zigzag Level Order Traversal