The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder…
2018
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 ______.
Attempted by 172 students.
Show answer & explanation
Correct answer: 4
Key idea: reconstruct the tree from postorder and inorder, then find the longest root-to-leaf path. The problem defines height as the length of that path (number of edges).
Root is 1 (last element of postorder). Inorder splits into left: 8,6,9,4,7,2,5 and right: 3, so the right child is 3 (a leaf).
For the left subtree (postorder segment 8,9,6,7,4,5,2), root is 2. Its inorder split gives left: 8,6,9,4,7 and right: 5, so 5 is the right child (a leaf).
For the left part of that subtree (postorder 8,9,6,7,4), root is 4. Inorder splits into left: 8,6,9 and right: 7, so 7 is the right child (a leaf).
For the left part of 4 (postorder 8,9,6), root is 6 with inorder left: 8 and right: 9, so 6 has children 8 and 9 (both leaves).
The longest root-to-leaf path is 1 → 2 → 4 → 6 → 8. This path has 4 edges, so the height (as defined) is 4.
A video solution is available for this question — log in and enroll to watch it.