To solve tree problems, you must be able to visit every node. There are two main ways: DFS (going deep) and BFS (scanning levels).

1. Depth First Search (DFS)

Think of a Labyrinth: You walk down one path as far as you can go. Only when you hit a dead end (Leaf) do you turn around and try the next path.

2. Breadth First Search (BFS)

Think of a Search Party: You scan the entire ground floor first. Only when the ground floor is clear do you move to the first floor, then the second.

---

DFS Flavors

1. Pre-order (Root, Left, Right): Used to clone a tree or evaluate prefix expressions.
2. In-order (Left, Root, Right): Crucial: Visiting a Binary Search Tree in-order gives you numbers in Sorted Order.
3. Post-order (Left, Right, Root): Used to delete a tree (children first, then root) or evaluate math expressions.

BFS (Level Order)

Uses a Queue instead of recursion. Good for finding the "shortest path" to a node.

---

javascript Standard
/**
 * DFS In-order (Recursive)
 */
function inOrder(root) {
  if (!root) return;
  inOrder(root.left);
  console.log(root.value); // Process Node
  inOrder(root.right);
}

/**
 * BFS Level-order (Iterative)
 */
function levelOrder(root) {
  if (!root) return [];
  const queue = [root];
  const result = [];

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

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

---

Visualizing Recursion

Don't get lost in the recursion stack. Use the Pointer Finger Rule: Trace the outside of the tree. When you pass the LEFT side of a node, it's Pre-order. When you pass the BOTTOM, it's In-order. When you pass the RIGHT, it's Post-order.

Common Questions

• Given Pre-order and In-order, reconstruct the tree.
• Zig-zag level order traversal.
• Find the maximum width of a tree.
• Identify the "View" of a tree (Left view, Right view).