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 (one way) or Linked Lists (one way), Trees have many ways to visit every node.

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

Breadth First Search (BFS)

Go wide before going deep.

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

2. Interactive Analysis

Select a mode and watch the order.

Order: []

3. Intuition: DFS vs BFS

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

DFS uses a Recursion Stack. Space is O(Height). Best for wide, shallow trees.
BFS uses a Queue. Space is O(Width). Best for deep, narrow trees (linked lists).

4. Implementation

Java

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

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