Tree Traversals

Concept

In an Array, there is only one way to traverse the data: for (let i=0; i<N).
In a Binary Tree, because of the branching paths, there are multiple mathematical ways to “visit” every node.

The two main categories of Tree Traversal are:

1. Depth-First Search (DFS): Plunge as deep as possible down one specific branch until you hit a leaf, then backtrack and try the next branch.
2. Breadth-First Search (BFS): Explore the tree horizontally, layer by layer.

Depth-First Search (DFS)

DFS is almost exclusively implemented using Recursion.
Because every node has three components (itself, its left child, and its right child), the order in which we process these three components gives us the three flavors of DFS:

1. Pre-order (NLR): Node -> Left -> Right.
2. In-order (LNR): Left -> Node -> Right.
3. Post-order (LRN): Left -> Right -> Node.

(Note: The name tells you exactly when the Node itself is processed. “Pre” means before its children. “In” means in between its children. “Post” means after its children).

Breadth-First Search (BFS)

BFS is implemented iteratively using a Queue.
It explores Level 0, then all nodes in Level 1, then all nodes in Level 2.

Level-Order Traversal:

1. Put the Root in a Queue.
2. Dequeue the Root. Process it.
3. Put its Left and Right children into the Queue.
4. Repeat until the Queue is empty.

When to use which?

Interviewers love to ask: “Why did you choose BFS instead of DFS for this problem?”

Choose DFS (Recursion) when:

• You need to search the absolute depths of a tree (e.g., finding the deepest leaf).
• You are answering questions about the paths from root to leaf.
• You want the code to be incredibly short and elegant (usually just 3 lines of code).
• You are executing a “Bottom-Up” algorithm (where a parent needs information from its children before it can calculate its own answer—use Post-order).

Choose BFS (Queue) when:

• You need to find the Shortest Path to something. (Because BFS searches level-by-level, the first time it finds the target, it is mathematically guaranteed to be the shortest path).
• You are answering questions about the horizontal relationships between nodes (e.g., “Right Side View of a Tree”, or “Connect nodes at the same level”).

Time and Space Complexity

Time Complexity:
For both DFS and BFS, the time complexity is strictly $O(N)$. To traverse an entire tree, you must visit every node exactly once. There is no escaping this math.

Space Complexity:

• DFS: Dictated by the Call Stack. In the worst case (a straight-line degenerate tree), the Call Stack gets $N$ frames deep, making it $O(N)$ space. In a perfectly balanced tree, the Call Stack only goes as deep as the height of the tree, making it $O(\log N)$ space.
• BFS: Dictated by the size of the Queue. In a perfectly balanced tree, the very bottom level holds exactly half of all the nodes in the tree ($N/2$). The Queue must hold all of them simultaneously. Therefore, BFS strictly requires $O(N)$ space.