PadhaikoAll subjects

Past exam question: 2078 Baishakh (Back), Q6

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

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

Question

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:

  1. Pre-order (Root -> Left -> Right): Visit root first, then left subtree, then right subtree.
  2. In-order (Left -> Root -> Right): Traverse left subtree, visit root, then traverse right subtree.
  3. Post-order (Left -> Right -> Root): Traverse left subtree, traverse right subtree, then visit root.
  4. (Also Breadth-First / Level-order traversal, visiting nodes level by level using a queue.)

Reconstruct Root and Subtrees from Pre-order & In-order:

Final Binary Tree:

               A
             /   \
            H     B
           / \     \
          G   I     C
             / \   /
            F   E D
Answer:

All past exam questions for Data Structure and Algorithms