GATE 2018 CS – Question 30
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 ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 4
Explanation
The root is 1 (last in postorder). Inorder splits into left $\{8,6,9,4,7,2,5\}$ and right $\{3\}$. The left root is 2, splitting $\{8,6,9,4,7\}$ and $\{5\}$, whose root is 4 with left $\{8,6,9\}$ and right $\{7\}$, and then 6 with children 8 and 9. The longest path is $1\to2\to4\to6\to8$, which has 4 edges.