Introduction: Navigating the Tree

Imagine you are standing at the entrance of a massive library where books are arranged in a Binary Tree structure. You need to check every single book, but you don't want to get lost or miss any branches. How do you do it systematically? This is where Tree Traversal comes in!

In this chapter, we will learn the different "roadmaps" used to visit every node in a tree. Whether you want to sort data, copy a structure, or search for a specific value, there is a specific traversal for the job. Don't worry if it seems like a lot of paths to remember; once you see the patterns, it becomes as simple as following a trail of breadcrumbs!

1. Depth-First Traversals

In Depth-First traversals, we try to go as "deep" as possible down one branch before backtracking and trying another. For Binary Trees, there are three main ways to do this, depending on when you "visit" (process) the root node relative to its children.

A. Pre-order Traversal (Root, Left, Right)

In Pre-order, you visit the Root first, then the Left subtree, and finally the Right subtree.

  • The Rule: Visit node \(\rightarrow\) Go Left \(\rightarrow\) Go Right.
  • Analogy: Think of this as a manager giving instructions. They speak first (Root), then the instruction travels down to the subordinates (Children).
  • Usage: Great for creating a copy of a tree or prefix notation in mathematics.

B. In-order Traversal (Left, Root, Right)

In In-order, you visit the Left subtree first, then the Root, and finally the Right subtree.

  • The Rule: Go Left \(\rightarrow\) Visit node \(\rightarrow\) Go Right.
  • Crucial H2 Syllabus Tip: For a Binary Search Tree (BST), an In-order traversal visits the nodes in ascending order (from smallest to largest)!
  • Usage: Used whenever you need to retrieve data in its sorted sequence.

C. Post-order Traversal (Left, Right, Root)

In Post-order, you visit the Left subtree, then the Right subtree, and finally the Root.

  • The Rule: Go Left \(\rightarrow\) Go Right \(\rightarrow\) Visit node.
  • Analogy: Like a graduation ceremony. The students (Children) must walk across the stage before the principal (Root) can close the ceremony.
  • Usage: Useful for deleting a tree (you delete the children before the parent) or evaluating postfix math expressions.

Quick Review Box:
Pre-order: Root is first.
In-order: Root is in the middle.
Post-order: Root is last.

2. The "Outline" Trick for Visualizing Traversals

If you are looking at a diagram of a tree in an exam, here is a foolproof trick to find the traversals without getting confused:

  1. Draw a single continuous line (a "hull") starting at the left of the root, hugging the edges of all nodes and branches until you return to the root.
  2. Pre-order: Mark the node when you pass its left side.
  3. In-order: Mark the node when you pass its bottom.
  4. Post-order: Mark the node when you pass its right side.
Try drawing a small tree with 3 nodes (A at the top, B on left, C on right) and trace it. You'll see In-order gives you B, A, C!

3. Breadth-First Search (BFS)

While Depth-First Search (DFS) dives deep, Breadth-First Search (BFS) explores the tree level by level.

Imagine a ripple in a pond. You start at the root (Level 0), then visit all nodes at Level 1, then all nodes at Level 2, moving from left to right across each level.

  • Mechanism: BFS uses a Queue (First-In, First-Out) data structure to keep track of which nodes to visit next.
  • The Process:
    1. Add the root to the Queue.
    2. While the queue is not empty:
      • Remove (dequeue) the front node and visit it.
      • Add (enqueue) all its children to the back of the queue.

Did you know? BFS is often used in social networks to find "friends of friends" because it finds the shortest path between nodes in an unweighted tree/graph!

4. Depth-First Search (DFS)

We already discussed the three types of depth-first traversals (Pre, In, Post). As a general Search strategy, DFS follows one path as far as it can go.

  • Mechanism: DFS uses a Stack (Last-In, First-Out). Because Recursion uses the "Call Stack" automatically, DFS is almost always implemented using a recursive function.
  • The Process:
    1. Start at the root.
    2. If the current node is what you are looking for, stop!
    3. If not, recursively call the DFS function on the left child, then the right child.

Key Comparison Table:

Feature Breadth-First Search (BFS) Depth-First Search (DFS)
Strategy Level by level (horizontal). Branch by branch (vertical).
Data Structure Queue (FIFO). Stack (LIFO) or Recursion.
Best for... Finding the shortest path. Exploring all possibilities/paths.

5. Algorithm Efficiency

In the Computing (9569) syllabus, we measure efficiency using Big-O Notation for time complexity.

For all tree traversals (Pre-order, In-order, Post-order, BFS, and DFS), we must visit every node exactly once to ensure we have seen everything.

Therefore, the Worst-Case Time Complexity is: \(O(n)\)

where \(n\) is the number of nodes in the tree. If you double the number of nodes, the time taken to traverse the tree will roughly double.

Summary & Key Takeaways

  • Traversing means visiting every node in a data structure once.
  • Pre-order, In-order, and Post-order are types of Depth-First traversals.
  • In-order traversal of a Binary Search Tree yields data in sorted order.
  • BFS uses a Queue and explores level by level.
  • DFS uses a Stack (often via recursion) and explores branch by branch.
  • All these traversals have a time complexity of \(O(n)\).

Note: For more information on how to build the trees themselves, refer to the "Binary Trees and Binary Search Trees" chapter. To understand how the Queue and Stack work behind the scenes, check the "Stacks and Queues" chapter.