Tree Traversal Algorithms - Complete Guide

Trees are hierarchical data structures that require specific traversal techniques. This guide covers all essential tree traversal algorithms and patterns.

Tree Basics #

Binary Tree Node #

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

// Create sample tree
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

//       1
//      / \
//     2   3
//    / \
//   4   5

Depth-First Traversals #

Inorder Traversal (Left-Root-Right) #

Recursive:

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

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

    traverse(node.left);
    result.push(node.val);
    traverse(node.right);
  }

  traverse(root);
  return result;
}

console.log(inorderTraversal(root));  // [4, 2, 5, 1, 3]

Iterative:

function inorderIterative(root) {
  const result = [];
  const stack = [];
  let current = 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);

    // Visit right subtree
    current = current.right;
  }

  return result;
}

Use Case: Get elements in sorted order (for BST)

Preorder Traversal (Root-Left-Right) #

Recursive:

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

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

    result.push(node.val);
    traverse(node.left);
    traverse(node.right);
  }

  traverse(root);
  return result;
}

console.log(preorderTraversal(root));  // [1, 2, 4, 5, 3]

Iterative:

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

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

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

    // Push right first so left is processed first
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }

  return result;
}

Use Case: Create a copy of tree, serialize tree

Postorder Traversal (Left-Right-Root) #

Recursive:

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

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

    traverse(node.left);
    traverse(node.right);
    result.push(node.val);
  }

  traverse(root);
  return result;
}

console.log(postorderTraversal(root));  // [4, 5, 2, 3, 1]

Iterative:

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

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

  while (stack.length > 0) {
    const node = stack.pop();
    result.unshift(node.val);  // Add to front

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

  return result;
}

Use Case: Delete tree, calculate directory size

Breadth-First Traversal #

Level Order Traversal #

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;
}

console.log(levelOrder(root));
// [[1], [2, 3], [4, 5]]

Use Case: Find shortest path, level by level processing

Zigzag Level Order #

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;
}

Vertical Order Traversal #

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

  const map = new Map();
  const queue = [[root, 0]];  // [node, column]

  while (queue.length > 0) {
    const [node, col] = queue.shift();

    if (!map.has(col)) {
      map.set(col, []);
    }
    map.get(col).push(node.val);

    if (node.left) queue.push([node.left, col - 1]);
    if (node.right) queue.push([node.right, col + 1]);
  }

  return Array.from(map.keys())
    .sort((a, b) => a - b)
    .map(col => map.get(col));
}

Common Tree Problems #

Maximum Depth #

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

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

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

Minimum Depth #

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

  if (!root.left) return minDepth(root.right) + 1;
  if (!root.right) return minDepth(root.left) + 1;

  return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

Path Sum #

function hasPathSum(root, targetSum) {
  if (!root) return false;

  if (!root.left && !root.right) {
    return root.val === targetSum;
  }

  return hasPathSum(root.left, targetSum - root.val) ||
         hasPathSum(root.right, targetSum - root.val);
}

All Root-to-Leaf Paths #

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

  function dfs(node, path) {
    if (!node) return;

    path.push(node.val);

    if (!node.left && !node.right) {
      result.push(path.join('->'));
    } else {
      dfs(node.left, [...path]);
      dfs(node.right, [...path]);
    }
  }

  dfs(root, []);
  return result;
}

Sum of Left Leaves #

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

  let sum = 0;

  if (root.left && !root.left.left && !root.left.right) {
    sum += root.left.val;
  }

  sum += sumOfLeftLeaves(root.left);
  sum += sumOfLeftLeaves(root.right);

  return sum;
}

Invert Binary Tree #

function invertTree(root) {
  if (!root) return null;

  [root.left, root.right] = [root.right, root.left];

  invertTree(root.left);
  invertTree(root.right);

  return root;
}

Symmetric Tree #

function isSymmetric(root) {
  function isMirror(left, right) {
    if (!left && !right) return true;
    if (!left || !right) return false;

    return left.val === right.val &&
           isMirror(left.left, right.right) &&
           isMirror(left.right, right.left);
  }

  return isMirror(root, root);
}

Same Tree #

function isSameTree(p, q) {
  if (!p && !q) return true;
  if (!p || !q) return false;

  return p.val === q.val &&
         isSameTree(p.left, q.left) &&
         isSameTree(p.right, q.right);
}

Subtree of Another Tree #

function isSubtree(root, subRoot) {
  if (!root) return false;

  if (isSameTree(root, subRoot)) return true;

  return isSubtree(root.left, subRoot) ||
         isSubtree(root.right, subRoot);
}

function isSameTree(p, q) {
  if (!p && !q) return true;
  if (!p || !q) return false;

  return p.val === q.val &&
         isSameTree(p.left, q.left) &&
         isSameTree(p.right, q.right);
}

Binary Search Tree Operations #

Validate BST #

function isValidBST(root) {
  function validate(node, min, max) {
    if (!node) return true;

    if (node.val <= min || node.val >= max) {
      return false;
    }

    return validate(node.left, min, node.val) &&
           validate(node.right, node.val, max);
  }

  return validate(root, -Infinity, Infinity);
}

Search in BST #

function searchBST(root, val) {
  if (!root || root.val === val) {
    return root;
  }

  if (val < root.val) {
    return searchBST(root.left, val);
  } else {
    return searchBST(root.right, val);
  }
}

Insert into BST #

function insertIntoBST(root, val) {
  if (!root) {
    return new TreeNode(val);
  }

  if (val < root.val) {
    root.left = insertIntoBST(root.left, val);
  } else {
    root.right = insertIntoBST(root.right, val);
  }

  return root;
}

Delete from BST #

function deleteNode(root, key) {
  if (!root) return null;

  if (key < root.val) {
    root.left = deleteNode(root.left, key);
  } else if (key > root.val) {
    root.right = deleteNode(root.right, key);
  } else {
    // Node to delete found

    // Case 1: Leaf node
    if (!root.left && !root.right) {
      return null;
    }

    // Case 2: One child
    if (!root.left) return root.right;
    if (!root.right) return root.left;

    // Case 3: Two children
    // Find inorder successor (smallest in right subtree)
    let successor = root.right;
    while (successor.left) {
      successor = successor.left;
    }

    root.val = successor.val;
    root.right = deleteNode(root.right, successor.val);
  }

  return root;
}

Kth Smallest in BST #

function kthSmallest(root, k) {
  const result = [];

  function inorder(node) {
    if (!node || result.length === k) return;

    inorder(node.left);

    if (result.length < k) {
      result.push(node.val);
    }

    inorder(node.right);
  }

  inorder(root);
  return result[k - 1];
}

Lowest Common Ancestor #

// For BST
function lowestCommonAncestorBST(root, p, q) {
  if (p.val < root.val && q.val < root.val) {
    return lowestCommonAncestorBST(root.left, p, q);
  }

  if (p.val > root.val && q.val > root.val) {
    return lowestCommonAncestorBST(root.right, p, q);
  }

  return root;
}

// For any 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;
}

Traversal Comparison #

Traversal	Order	Use Case
Inorder	Left-Root-Right	BST sorted order
Preorder	Root-Left-Right	Copy tree, serialize
Postorder	Left-Right-Root	Delete tree, calculate size
Level Order	Level by level	Shortest path, BFS

Time and Space Complexity #

Operation	Time	Space
DFS Traversal	O(n)	O(h)
BFS Traversal	O(n)	O(w)
Search (BST)	O(h)	O(h)
Insert (BST)	O(h)	O(h)
Delete (BST)	O(h)	O(h)

Where:

n = number of nodes
h = height of tree
w = maximum width

Common Patterns #

DFS for path problems - Use recursion to explore paths
BFS for level problems - Use queue for level order
Inorder for BST - Get sorted elements
Postorder for bottom-up - Process children first
Track parent/level - Pass extra parameters in recursion

Tips #

Draw the tree - Visualize the problem
Identify traversal type - Match problem to traversal
Handle null cases - Always check for null nodes
Consider leaf nodes - Special case with no children
Use helper functions - Pass extra parameters in recursion
Stack for iterative DFS - Queue for BFS
Path tracking - Use arrays to track paths

Tree traversals are fundamental for solving tree and graph problems. Master these patterns and you’ll be able to tackle any tree challenge efficiently.