L4. Binary Tree Traversals in Binary Tree | BFS | DFS

Navigating, inspecting, or solving problems on trees fundamentally requires visiting every single node in a specific, systematic order. This chapter explores the two primary tree traversal strategies: Depth First Search (DFS)—further broken down into Inorder, Preorder, and Postorder traversals—and Breadth First Search (BFS), which operates level by level.

1. Why Do We Need Tree Traversals?

In linear data structures like arrays, linked lists, or stacks, elements are stored sequentially, making traversal straightforward (from index $0$ to $N-1$). However, hierarchical structures like trees scatter nodes across multiple branches and levels.

• The Problem: You cannot simply use a single loop to visit every node because there is no single linear path.
• The Requirement: To search for an element, print values, calculate heights, or serialize a tree, you need a deterministic strategy to visit every node exactly once without getting lost in branches.
• The Solution: Tree traversal algorithms provide exact roadmaps, categorized into two broad families:
  1. Depth First Search (DFS): Dive deep down the subtrees first before exploring neighbors.
  2. Breadth First Search (BFS): Explore all nodes at the present depth (level by level) before moving to the next level.

2. Core Mental Model: DFS vs. BFS

To intuitively grasp the difference between the two traversal families, consider how you would explore a multi-room building or a corporate hierarchy:

• DFS (Depth First Search): Imagine entering a large building, walking down the leftmost corridor, entering the first room on the left, walking into its innermost closet, exploring everything down that specific vertical path to the very bottom, and only backing up when you hit a dead end.
• BFS (Breadth First Search): Imagine standing on the ground floor and inspecting every room on the ground floor from left to right before walking up the stairs to inspect every room on the first floor, and so on, level by level.

3. Depth First Search (DFS) Fundamentals

Depth First Search explores a tree by going as deep as possible along each branch before backtracking. Depending on when you process the current node (the root) relative to its left and right subtrees, DFS splits into three distinct variants:

Note: Whenever you apply these formulas to a subtree, treat that subtree as an independent mini-tree with its own root, left child, and right child. Recursion naturally handles this propagation.

4. Detailed Walkthrough 1: Standard Tree DFS

Consider a sample binary tree structured as follows:

• Root: 1
• Left Subtree of 1: Root 2, with left child 4 and right child 5
• Right Subtree of 1: Root 3, with left child 6 and right child 7

         1
       /   \
      2     3
     / \   / \
    4   5 6   7

A. Inorder Traversal (Left $\rightarrow$ Root $\rightarrow$ Right)

1. Go to the extreme left subtree (Node 2's left subtree, which is 4).
2. Apply Inorder on subtree rooted at 2:
   • Left: 4
   • Root: 2
   • Right: 5
   • Result for left side: 4, 2, 5
3. Process the main root: 1
4. Go to the right subtree (Node 3), applying Left $\rightarrow$ Root $\rightarrow$ Right:
   • Left: 6
   • Root: 3
   • Right: 7
   • Result for right side: 6, 3, 7

• Final Inorder Traversal Output: 4, 2, 5, 1, 6, 3, 7

B. Preorder Traversal (Root $\rightarrow$ Left $\rightarrow$ Right)

1. Process the main root first: 1
2. Go to the left subtree (Node 2), applying Root $\rightarrow$ Left $\rightarrow$ Right:
   • Root: 2
   • Left: 4
   • Right: 5
   • Result for left side: 2, 4, 5
3. Go to the right subtree (Node 3), applying Root $\rightarrow$ Left $\rightarrow$ Right:
   • Root: 3
   • Left: 6
   • Right: 7
   • Result for right side: 3, 6, 7

• Final Preorder Traversal Output: 1, 2, 4, 5, 3, 6, 7

C. Postorder Traversal (Left $\rightarrow$ Right $\rightarrow$ Root)

1. Go to the left subtree (Node 2), applying Left $\rightarrow$ Right $\rightarrow$ Root:
   • Left: 4
   • Right: 5
   • Root: 2
   • Result for left side: 4, 5, 2
2. Go to the right subtree (Node 3), applying Left $\rightarrow$ Right $\rightarrow$ Root:
   • Left: 6
   • Right: 7
   • Root: 3
   • Result for right side: 6, 7, 3
3. Process the main root last: 1

• Final Postorder Traversal Output: 4, 5, 2, 6, 7, 3, 1

5. Detailed Walkthrough 2: Modified Larger Tree DFS

Let's expand our tree to test our recursive mental model on a slightly more complex structure:

           1
         /   \
        2     3
       / \   / \
      4   5 6   7
     /         / \
    8         9  10

A. Inorder Traversal (Left $\rightarrow$ Root $\rightarrow$ Right)

1. Left Subtree (Root 2):
   • Its left child is 4, which has a left child 8.
   • Traversing 4's subtree (Left $\rightarrow$ Root $\rightarrow$ Right): 8, 4.
   • Then root 2, then right 5.
   • Subtree result: 8, 4, 2, 5.
2. Main Root: 1.
3. Right Subtree (Root 3):
   • Left is 6.
   • Root is 3.
   • Right is subtree 7 with children 9 (left) and 10 (right). Applying Inorder on 7's subtree gives 9, 7, 10.
   • Subtree result: 6, 3, 9, 7, 10.

• Final Inorder Traversal Output: 8, 4, 2, 5, 1, 6, 3, 9, 7, 10

B. Preorder Traversal (Root $\rightarrow$ Left $\rightarrow$ Right)

1. Main Root: 1.
2. Left Subtree (Root 2):
   • Root: 2
   • Left branch: 4 (which has left child 8) $\rightarrow$ Root 4, Left 8.
   • Right branch: 5.
   • Subtree result: 2, 4, 8, 5.
3. Right Subtree (Root 3):
   • Root: 3
   • Left: 6
   • Right branch (Root 7 with children 9 and 10) $\rightarrow$ Root 7, Left 9, Right 10.
   • Subtree result: 3, 6, 7, 9, 10.

• Final Preorder Traversal Output: 1, 2, 4, 8, 5, 3, 6, 7, 9, 10

C. Postorder Traversal (Left $\rightarrow$ Right $\rightarrow$ Root)

1. Left Subtree (Root 2):
   • Leftmost path: node 8 is processed, then node 4's right is empty, then root 4. So 8, 4.
   • Right child of 2: 5.
   • Root of subtree: 2.
   • Subtree result: 8, 4, 5, 2.
2. Right Subtree (Root 3):
   • Left child: 6.
   • Right subtree rooted at 7 (left 9, right 10, root 7) $\rightarrow$ 9, 10, 7.
   • Root of subtree: 3.
   • Subtree result: 6, 9, 10, 7, 3.
3. Main Root: 1.

• Final Postorder Traversal Output: 8, 4, 5, 2, 6, 9, 10, 7, 1

6. Breadth First Search (BFS) Traversal

While DFS dives deep into branches using recursion or stacks, Breadth First Search (BFS) inspects trees horizontally, level by level.

• Level-Order Nature: BFS processes all nodes at depth $0$ (the root), then all nodes at depth $1$ (children of root), then depth $2$ (grandchildren), and so on.
• Simplicity: Conceptually, BFS is often considered more intuitive because it mirrors natural layer-by-layer scanning.

Using our standard tree:

         1
       /   \
      2     3
     / \   / \
    4   5 6   7

• Level 0: 1
• Level 1: 2, 3
• Level 2: 4, 5, 6, 7
• Final BFS Traversal Output: 1, 2, 3, 4, 5, 6, 7

7. Practical Study Guide & Mastery Technique

If tree traversals feel confusing or abstract at first glance, do not worry—this is a universal hurdle in Data Structures & Algorithms.

Expert Recommendation: Do not rely solely on mental visualization. Take a blank sheet of paper or a notebook, draw 10 random binary trees of varying shapes and depths, and manually write out their Inorder, Preorder, Postorder, and BFS traversals. Doing this consistently for a few days builds unbreakable intuition.

Summary and Key Takeaways

• Tree Traversals: Essential techniques required to visit every node in a tree systematically to solve algorithmic problems.
• Depth First Search (DFS): Explores deep down subtrees before backtracking, dividing into three variants based on root placement.
• Inorder Traversal: Follows the Left -> Root -> Right sequence.
• Preorder Traversal: Follows the Root -> Left -> Right sequence (root is visited before subtrees).
• Postorder Traversal: Follows the Left -> Right -> Root sequence (root is visited after subtrees).
• Mnemonic Rule: "Pre" = Root first; "In" = Root in middle; "Post" = Root last.
• Breadth First Search (BFS): Explores trees horizontally, visiting nodes level by level from top to bottom.
• Practice Routine: Drawing custom trees on paper and manually working through recursive subtree expansions is the fastest path to algorithmic mastery.