GATE CS 2018 Q20 — Trees

To find the height of the binary tree, we first reconstruct the tree using its postorder and inorder traversals.

In a postorder traversal, the root node is always visited last. In an inorder traversal, the root node splits the sequence into left and right subtrees.

• The last element of the postorder traversal is 1, which is the root.
• Splitting the inorder traversal around 1 gives:
  • Left subtree: {8, 6, 9, 4, 7, 2, 5}
  • Right subtree: {3}

Repeating this process recursively, we reconstruct the unique binary tree structure:

• 1 is the root. Its left child is 2, and its right child is 3.
• 2 has left child 4 and right child 5.
• 4 has left child 6 and right child 7.
• 6 has left child 8 and right child 9.

The paths from the root 1 to the leaf nodes are:

• $1 o 3$ (length 1)
• $1 o 2 o 5$ (length 2)
• $1 o 2 o 4 o 7$ (length 3)
• $1 o 2 o 4 o 6 o 8$ (length 4)
• $1 o 2 o 4 o 6 o 9$ (length 4)

The height of the tree is the length of the longest path from the root to any leaf, which is $\mathbf{4}$.