IAE Academy

GATE 2018 CS Q.20: solution and answer

GATE 2018 · CSQ.20 · 1 mark · NAT

The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of the same tree is 8,6,9,4,7,2,5,1,3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is ______.

See the question in the paper
GATE 2018 CS question 20Tap to open full size

Answer and solution

ANSWER

The height of the binary tree is 4.

Official answer: 4Source: Official answer key, GATE 2018 CS (IIT Guwahati)

  1. Root of the tree = last element of postorder = 1.

  2. In inorder, 1 splits the sequence into left subtree {8,6,9,4,7,2,5} (7 nodes) and right subtree {3} (1 node); matching postorder sizes give left postorder = first 7 elements {8,9,6,7,4,5,2}, right postorder = last 1 element {3}.

  3. Right subtree of 1 is a single node 3 — a leaf at depth 1.

  4. Left subtree root = last of postorder {8,9,6,7,4,5,2} = 2. Inorder split by 2: left {8,6,9,4,7} (5 nodes), right {5} (1 node) — a leaf at depth 2.

  5. Root of {8,6,9,4,7} with postorder {8,9,6,7,4} is 4 (last element). Inorder split by 4: left {8,6,9} (3 nodes), right {7} (1 node) — a leaf at depth 3.

  6. Root of {8,6,9} with postorder {8,9,6} is 6 (last element). Inorder split by 6: left {8} (leaf) and right {9} (leaf), both at depth 4.

  7. Longest root-to-leaf path: 1 → 2 → 4 → 6 → 8 (or 9), which contains 4 edges.

  8. Height (edge count of the longest root-to-leaf path, as defined in the question) = 4.

KEY IDEA

Reconstruct the binary tree from postorder and inorder traversals recursively: the last element of a postorder segment is the subtree's root; its position in the corresponding inorder segment splits the remaining nodes into left and right subtrees, and the sizes of these splits also split the postorder segment (left-subtree postorder is the first |left| elements, right-subtree postorder is the last |right| elements). Recursing down the always-larger left branch reveals the tree's shape without drawing every node's siblings.

WATCH OUT FOR

Confusing "height" (edge count of the longest root-to-leaf path, as this question explicitly defines it) with "number of levels" or "number of nodes on the longest path" (which would give 5 instead of 4); also, when splitting the postorder sequence by subtree size, using the wrong slice boundaries (e.g., taking the left postorder segment from the end instead of the start) can silently misassign which node is which subtree's root.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 26 Trees & heaps questions, with notes

More Trees & heaps questions