Past exam question: 2078 Poush (Back), Q6(a)
Open in the Padhaiko appQuestion
Construct a binary tree from its given pre-order and in-order traversals. Pre order: A, H, G, I, F, E, B, C, D In order: G, H, F, I, E, A, B, D, C
Solution
Identify Root and Left/Right Subtree Partitions: The first element of Pre-order (A) is the root. Searching A in In-order G, H, F, I, E, [A], B, D, C:
- Left subtree In-order:
G, H, F, I, Ecorresponding Pre-order (next 5 elements):H, G, I, F, E. - Right subtree In-order:
B, D, Ccorresponding Pre-order (last 3 elements):B, C, D.
Construct Left Subtree of A: Pre-order H, G, I, F, E, In-order G, H, F, I, E:
- Root is
H. In In-order: left =G, right =F, I, E(Pre-orderI, F, E). - For right child (
I, F, E/F, I, E): root isI, left child isF, right child isE.
Construct Right Subtree of A: Pre-order B, C, D, In-order B, D, C:
- Root is
B. In In-order: left = (empty), right =D, C(Pre-orderC, D). - For right child (
C, D/D, C): root isC, left child isD, right = (empty).
Reconstructed Binary Tree and Verification:
A
/ \
H B
/ \ \
G I C
/ \ /
F E D
- Pre-order:
A, H, G, I, F, E, B, C, D(matches). - In-order:
G, H, F, I, E, A, B, D, C(matches).
Answer:
The reconstructed binary tree has root A, left subtree H (left G, right I with children F and E), and right subtree B (right C with left child D).