Tree Traversals

Why Traverse a Tree?

When you have a tree, you often need to visit every node — maybe to print values, search for something, or calculate a sum. That's where tree traversals come in. They're just different orders of visiting nodes.

Think of it like visiting rooms in a building. Do you visit the ground floor rooms first, then go up? Or do you visit the whole left wing before the right wing? The order matters because it affects what you can do efficiently.

There are four main traversals: in-order, pre-order, post-order, and level-order. Each has its own use case, and knowing when to use which is the key skill.

In-Order Traversal

In-order means: visit the left subtree, then the root, then the right subtree. It's like reading a book — you read the left page, then the current page, then the right page.

The cool thing about in-order traversal on a BST is that it visits nodes in sorted order. If you print values during an in-order traversal, you get a sorted list. That's incredibly useful for validation and debugging.

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

function inOrder(node) {
  if (!node) return [];
  return [...inOrder(node.left), node.value, ...inOrder(node.right)];
}

function preOrder(node) {
  if (!node) return [];
  return [node.value, ...preOrder(node.left), ...preOrder(node.right)];
}

function postOrder(node) {
  if (!node) return [];
  return [...postOrder(node.left), ...postOrder(node.right), node.value];
}

const root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(6);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);

console.log(inOrder(root));
console.log(preOrder(root));
console.log(postOrder(root));

Pre-Order and Post-Order

Pre-order visits the root first, then left, then right. It's great for copying a tree — you create the parent before the children, so references work naturally. Serializing a tree for storage? Use pre-order.

Post-order visits left, right, then root. It's perfect for deleting a tree — you delete children before the parent, so you don't orphan anything. Calculating directory sizes? Post-order, since you need subfolder sizes before the parent folder.

Level-order traversal (BFS) visits nodes level by level, left to right. It uses a queue instead of recursion. It's great for finding the shortest path or printing a tree level by level.

function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];

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

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

console.log(levelOrder(root));