Walking the Tree

Unlike Arrays (one way) or Linked Lists (one way), Trees have many ways to visit every node. The choice of traversal fundamentally dictates the order in which we process data and the hardware constraints we will hit.

1. Depth First Search (DFS)

Think of DFS like a maze explorer who picks a path and goes as deep as possible until they hit a dead end, then backtracks. It explores vertically.

  • Preorder (N-L-R): Root, Left, Right. You visit the node first, then its children. (Used for copying trees or serializing structure).
  • Inorder (L-N-R): Left, Root, Right. You visit the left subtree, then the node, then the right. (Crucial: This visits nodes in sorted order for Binary Search Trees!).
  • Postorder (L-R-N): Left, Right, Root. You visit the children before the node itself. (Used for deleting trees or calculating directory sizes from bottom-up).

2. Breadth First Search (BFS)

Think of BFS like a water ripple spreading outward from a thrown stone. It explores horizontally, visiting all neighbors at the current depth before moving deeper.

  • Level Order: Row by row, top to bottom, left to right. (Used for finding the shortest path in unweighted graphs or discovering the closest nodes first).

3. Hardware Truth: Traversal Memory Profile

Choosing between DFS and BFS isn’t just about the “order” of nodes. It’s fundamentally about your RAM and how you traverse memory.

Metric Depth-First Search (DFS) Breadth-First Search (BFS)
Space O(\text{Height}) O(\text{Width})
Structure Recursion Stack Queue (FIFO)
Worst Case A single “Stick” (Deep tree) A “Full” tree (Wide base)

Pro-Tip for Heroes:

  • Use DFS if the tree is very wide but shallow (like a flat file system). DFS uses the Call Stack, meaning memory usage scales with the depth of the tree O(H).
  • Use BFS if the tree is very deep but narrow (like a long linked list). BFS uses a Queue allocated on the Heap, meaning memory usage scales with the widest level of the tree O(W).

4. Interactive: Traversal Animator

Select a mode and watch the order.

Order: []

5. Implementation

Java

// Preorder: Root -> Left -> Right
public void preorder(TreeNode root) {
  if (root == null) return;
  System.out.print(root.val + " ");
  preorder(root.left);
  preorder(root.right);
}

// Inorder: Left -> Root -> Right
public void inorder(TreeNode root) {
  if (root == null) return;
  inorder(root.left);
  System.out.print(root.val + " ");
  inorder(root.right);
}

Go

func Preorder(root *TreeNode) {
  if root == nil { return }
  fmt.Print(root.Val, " ")
  Preorder(root.Left)
  Preorder(root.Right)
}

func Inorder(root *TreeNode) {
  if root == nil { return }
  Inorder(root.Left)
  fmt.Print(root.Val, " ")
  Inorder(root.Right)
}