Binary Tree Traversal: In-order, Pre-order, and Post-order traversal

[qingquan-li]

Binary Tree Traversal refers to the process of visiting each node in a binary tree exactly once in a specific order. The three common methods of traversal (Depth-First Traversal) in binary trees are In-order, Pre-order, and Post-order traversal:

• In-order Traversal: Visit the left branch, then the current node, and finally, the right branch. This gives nodes in non-decreasing order for binary search trees.
• Pre-order Traversal: Visit the current node before its child nodes.
• Post-order Traversal: Visit the current node after its child nodes.

Each of these methods has its own applications and uses:

• In-order Traversal: Mainly used in binary search trees where it returns nodes sorted in a non-decreasing order.
• Pre-order Traversal: Can be used to create a copy of the tree or to get prefix expression on an expression tree.
• Post-order Traversal: Useful for deleting the tree or to get the postfix expression of an expression tree.

1. In-order Traversal

In-order traversal means visiting the left subtree, then the current node, and finally the right subtree. This is commonly used because it visits nodes in an ascending order in binary search trees.

A binary search tree is a node-based binary tree where each node has a comparable key, and the keys in the left subtree of a node are less than the node's key, while those in the right subtree are greater.

Example BST:

    8
   / \
  3   10
 / \    \
1   6    14
   / \   /
  4   7 13

Steps for In-order Traversal

1. Traverse the left subtree in an in-order manner.
2. Visit the current node (process the data of the node).
3. Traverse the right subtree in an in-order manner.

Example: a simple binary tree for In-order Traversal

    A
   / \
  B   C
 / \
D   E

Traversal Order: D, B, E, A, C.

Example: a more complex binary tree for In-order Traversal

    A
   / \
  B   C
 /   / \
D   E   F
   /   /
  G   H

1. Start with the leftmost node D, then visit B.
2. Move up to A.
3. Traverse to A's right subtree: first visit G (left child of E), then E, up to C.
4. Finally, visit H and then F.

Traversal Order: D, B, A, G, E, C, H, F

2. Pre-order Traversal

Pre-order traversal means visiting the current node before its child nodes. In other words, you process the current node and then perform pre-order traversal of the left and right subtrees.

Steps for Pre-order Traversal

1. Visit the current node.
2. Traverse the left subtree in a pre-order manner.
3. Traverse the right subtree in a pre-order manner.

Example: a simple binary tree for Pre-order Traversal

    A
   / \
  B   C
 / \
D   E

Traversal Order: A, B, D, E, C.

Example: a more complex binary tree for Pre-order Traversal

    A
   / \
  B   C
 /   / \
D   E   F
   /   /
  G   H

1. Start with A.
2. Move down to B, then to its left child D.
3. Go back up and across to C, then down to E, and to its left child G.
4. Finally, move to F and its left child H.

Traversal Order: A, B, D, C, E, G, F, H

3. Post-order Traversal

Post-order traversal means visiting the current node after its child nodes. In this method, the traversal happens first on the left subtree, then the right subtree, and finally the current node.

Steps for Post-order Traversal

1. Traverse the left subtree in a post-order manner.
2. Traverse the right subtree in a post-order manner.
3. Visit the current node.

Example: a simple binary tree for Post-order Traversal

    A
   / \
  B   C
 / \
D   E

Traversal Order: D, E, B, C, A.

Example: a more complex binary tree for Post-order Traversal

    A
   / \
  B   C
 /   / \
D   E   F
   /   /
  G   H

1. Start with D (leftmost node), move up to B.
2. Traverse C's left subtree: visit G, then E.
3. Visit H (left child of F), then F itself.
4. Move up to C, and finally to the root A.

Traversal Order: D, B, G, E, H, F, C, A