Walking the Tree

Unlike Arrays (one way) or Linked Lists (one way), Trees have many ways to visit every node.

1. Depth First Search (DFS)

Go deep before going wide.

• Preorder (N-L-R): Root, Left, Right. (Used for copying trees).
• Inorder (L-N-R): Left, Root, Right. (Sorted order for BSTs!).
• Postorder (L-R-N): Left, Right, Root. (Used for deleting trees).

2. Breadth First Search (BFS)

Go wide before going deep.

• Level Order: Row by row. (Used for finding shortest path in unweighted graphs).

---

3. Hardware Truth: Traversal Memory Profile

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

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).
• Use BFS if the tree is very deep but narrow (like a long linked list).

---

4. Interactive: Traversal Animator

Select a mode and watch the order.

Preorder (NLR) Inorder (LNR) Postorder (LRN) Level Order (BFS)

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