PadhaikoAll subjects

Past exam question: 2078 Poush (Back), Q6(a)

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

Topic: Definition and tree terminologies · Binary trees · Binary search tree

Question

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:

Construct Left Subtree of A: Pre-order H, G, I, F, E, In-order G, H, F, I, E:

Construct Right Subtree of A: Pre-order B, C, D, In-order B, D, C:

Reconstructed Binary Tree and Verification:

               A
             /   \
            H     B
           / \     \
          G   I     C
             / \   /
            F   E D
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).

All past exam questions for Data Structure and Algorithms