Trees are a fundamental and important data structure in programming, with familiar applications such as file directories, binary search trees, and database indexes, all leveraging tree structures. “Traversal” refers to the process of visiting every node in a tree, much like exploring all attractions in a park. Today, we’ll discuss tree traversal, particularly the most common ones: pre-order, in-order, and post-order traversal, to help you easily understand their differences and usage.

Basic Concepts of Trees¶

First, let’s briefly review tree structures:
A tree consists of nodes, where each node can have 0 or more child nodes (subtrees). The topmost node is called the “root,” and nodes with no children are called “leaves.” Here, we focus on binary trees (each node has at most 2 children: left and right subtrees).

The Core of Traversal: Visit Order¶

The key difference between the three traversal methods lies in the timing of visiting the root node. Let’s use a concrete binary tree example to demonstrate. The tree structure is as follows (root is 1, left child is 2, right child is 3; 2 has left child 4 and right child 5; 3 has left child 6 and right child 7):

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

1. Pre-order Traversal: Root → Left → Right¶

Rule: Visit the root node first, then recursively traverse the left subtree, and finally the right subtree.
Steps:
- Visit root node 1;
- Recursively traverse the left subtree (root 2): visit 2, then traverse 2’s left subtree (4), then 2’s right subtree (5);
- Recursively traverse the right subtree (root 3): visit 3, then traverse 3’s left subtree (6), then 3’s right subtree (7).

Result: 1 → 2 → 4 → 5 → 3 → 6 → 7.

2. In-order Traversal: Left → Root → Right¶

Rule: Recursively traverse the left subtree first, then visit the root node, and finally the right subtree.
Steps:
- Recursively traverse the left subtree (root 2): traverse 2’s left subtree (4), visit 2, then traverse 2’s right subtree (5);
- Visit root node 1;
- Recursively traverse the right subtree (root 3): traverse 3’s left subtree (6), visit 3, then traverse 3’s right subtree (7).

Result: 4 → 2 → 5 → 1 → 6 → 3 → 7.

3. Post-order Traversal: Left → Right → Root¶

Rule: Recursively traverse the left subtree first, then the right subtree, and finally visit the root node.
Steps:
- Recursively traverse the left subtree (root 2): traverse 2’s left subtree (4), then 2’s right subtree (5), then visit 2;
- Recursively traverse the right subtree (root 3): traverse 3’s left subtree (6), then 3’s right subtree (7), then visit 3;
- Visit root node 1.

Result: 4 → 5 → 2 → 6 → 7 → 3 → 1.

Comparison of the Three Traversals¶

To clarify, we summarize with mnemonics and results:

Key Memory Point: Pre-order (root first), In-order (root in the middle), Post-order (root last).

Practical Applications of Traversal¶

Understanding the purpose of traversal helps you master its usage:
- Pre-order Traversal: Commonly used to copy tree structures (e.g., deep copying a binary tree: copy the root first, then left and right subtrees).
- In-order Traversal: In a binary search tree (where left subtree values < root value < right subtree values), in-order traversal yields a sorted sequence from smallest to largest, a core logic for sorting.
- Post-order Traversal: Often used for node deletion or calculating tree depth (e.g., deleting a node requires deleting left and right subtrees first before the root).

Conclusion¶

Tree traversal is essentially an application of recursive thinking—breaking down a large problem into smaller subproblems, where each subtree is processed with the same rule. While it may seem complex at first, drawing the tree and walking through examples repeatedly will quickly make it intuitive. Remember the traversal orders (root-left-right, left-root-right, left-right-root) and their use cases (e.g., in-order for sorting, post-order for deletion), and you’ll master tree traversal easily!