Past exam question: 2078 Baishakh (Back), Q6
Open in the Padhaiko appQuestion
What are different traversal methods in tree? Construct a binary tree from its given pre-order and in-order traversal. Pre-order: A H G I F E B C D In-order: G H F I E A B D C
Solution
Binary Tree Traversal Methods:
- Pre-order (
Root -> Left -> Right): Visit root first, then left subtree, then right subtree. - In-order (
Left -> Root -> Right): Traverse left subtree, visit root, then traverse right subtree. - Post-order (
Left -> Right -> Root): Traverse left subtree, traverse right subtree, then visit root. - (Also Breadth-First / Level-order traversal, visiting nodes level by level using a queue.)
Reconstruct Root and Subtrees from Pre-order & In-order:
- Root = first symbol of Pre-order =
A. - Splitting In-order at
A:- Left In-order:
G H F I ELeft Pre-order:H G I F E.- Root
HsplitsG | H | F I E: left child isG; right subtree (I F E/F I E) has rootIwith leftFand rightE.
- Root
- Right In-order:
B D CRight Pre-order:B C D.- Root
Bsplits| B | D C: no left child; right subtree (C D/D C) has rootCwith left childD.
- Root
- Left In-order:
Final Binary Tree:
A
/ \
H B
/ \ \
G I C
/ \ /
F E DAnswer:
- Traversal Methods: Pre-order (
N-L-R), In-order (L-N-R), Post-order (L-R-N), plus Level-order. - Constructed Tree: Root
A, left childH(leftG, rightIwith childrenF, E), right childB(rightCwith left childD).