Past exam question: 2078 Poush (Back), Q6(b)
Open in the Padhaiko appQuestion
Briefly explain pre-order, in-order, post-order tree traversal methods with example.
Solution
Three Depth-First Binary Tree Traversal Orders:
- Pre-order (
Root -> Left -> Right): Visit the root first, then recursively traverse the left subtree, then the right subtree. Used to clone a tree or produce prefix expressions. - In-order (
Left -> Root -> Right): Traverse left subtree, visit root, then traverse right subtree. Produces sorted output on a Binary Search Tree. - Post-order (
Left -> Right -> Root): Traverse left subtree, traverse right subtree, then visit root last. Used to free/delete nodes bottom-up or produce postfix expressions.
Example on a Small Binary Tree:
+
/ \
A B
- Pre-order:
+ A B - In-order:
A + B - Post-order:
A B +
Answer:
- Pre-order (N-L-R):
+ A B - In-order (L-N-R):
A + B - Post-order (L-R-N):
A B +