Walking the Tree

[!NOTE] This module explores the core principles of Tree Traversals (DFS & BFS), deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

Unlike Arrays or Linked Lists where there is only a single logical path forward, Trees offer multiple distinct traversal strategies. The choice of traversal dictates the order in which we process data.

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.

• 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).

Breadth First Search (BFS)

Think of BFS like a water ripple spreading outward from a thrown stone. It explores 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).

---

2. Interactive Analysis

Select a mode and watch the order.

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

Order: []

---

3. Intuition: DFS vs BFS

Choosing between DFS and BFS isn’t merely an algorithmic preference; it fundamentally comes down to hardware constraints and RAM utilization.

• DFS (Call Stack Constraint): DFS relies on the system’s recursion call stack (or an explicit stack). The space complexity is proportional to the height of the tree, O(H). If the tree is wide but shallow, DFS is extremely memory efficient. However, if the tree is a degenerated deep line (like a linked list), a deep DFS can cause a StackOverflowError.
• BFS (Heap Memory Constraint): BFS relies on a Queue allocated on the heap. The space complexity is proportional to the maximum width of the tree, O(W). In a perfectly balanced binary tree, the bottom level holds N/2 nodes. This means BFS can consume massive amounts of memory for very wide trees, but is perfectly safe for deep, narrow structures.

---

4. Implementation

Java

Go

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

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

---

5. Complexity Analysis

Metric	Depth-First Search (DFS)	Breadth-First Search (BFS)
Time	O(N)	O(N)
Space	O(Height)	O(Width)
Structure	Stack (Recursion)	Queue