Q14Data Structures

A unique, structurally sound binary tree can be logically and deterministically reconstructed if and only if both its In-order traversal and its Pre-order (or alternatively, Post-order) traversal sequences are provided. The fundamental algorithmic strategy relies heavily on the inherent definitions of these traversal methods. The Pre-order traversal sequence strictly guarantees that the absolute first element encountered is unequivocally the overarching root of the current tree or subtree. Conversely, the In-order traversal sequence provides crucial topological mapping: locating that established root element within the In-order sequence instantaneously partitions all remaining elements into two distinct, mutually exclusive subsets representing the entire left subtree and the entire right subtree.

Reconstruction Step-by-Step

We are provided with the following sequences: In-order: Q, B, K, C, F, A, G, P, E, D, H, R Pre-order: G, B, Q, A, C, K, F, P, D, E, R, H

Step 1 (Root Identification): Analyzing the Pre-order sequence, the very first element is G. Therefore, node G is the absolute root of the entire binary tree. Step 2 (Partitioning): We locate G within the In-order sequence. The sequence splits perfectly around G: Left Subtree Elements: {Q, B, K, C, F, A} Right Subtree Elements: {P, E, D, H, R}

Step 3 (Reconstructing the Left Subtree): We filter the Pre-order sequence for only the left elements: B, Q, A, C, K, F. The first element is B, making it the root of the left subtree (child of G). Locating B in the left In-order subset (Q, B, K, C, F, A) shows Q is to its left (left child of B), and {K, C, F, A} is to its right. Filtering Pre-order for this right subset yields A, C, K, F. Thus, A is the right child of B. In In-order {K, C, F, A}, A is at the end, meaning {K, C, F} forms its left subtree. Pre-order for this is C, K, F. So, C is the left child of A. In-order for C is K, C, F, making K the left child and F the right child of C.

Step 4 (Reconstructing the Right Subtree): We filter the Pre-order sequence for the right elements: P, D, E, R, H. The first element is P, making it the right child of the main root G. Locating P in the right In-order subset (P, E, D, H, R) shows it has no left children, and {E, D, H, R} forms its right subtree. Pre-order for this is D, E, R, H. So, D is the right child of P. In-order for D is E, D, H, R, making E the left child of D, and {H, R} the right subtree. Pre-order for this is R, H. So R is the right child of D. In-order is H, R, making H the left child of R.