The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2018 GATE-CS Data Structures paper.

Q: How can I prepare for GATE-CS Data Structures?

To prepare for GATE-CS Data Structures, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2018 question covers Trees and Binary Trees topic.

Q: What is the difficulty level of this question?

This GATE-CS 2018 Data Structures question has a hard difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

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 the binary tree is _______.(Height = length of longest path from root to any leaf, measured in number of edges)

Accepted Answer

Correct Answer: 4Step-by-step Solution:The last element of postorder traversal is always the root: root = 1.In the inorder sequence, 1 appears at position 8 (1-indexed). Elements to its left form the left subtree inorder = {8, 6, 9, 4, 7, 2, 5} (7 nodes), and elements to its right form the right subtree inorder = {3} (1 node).The first 7 elements of postorder form the left subtree postorder = {8, 9, 6, 7, 4, 5, 2}, and the next 1 element is the right subtree postorder = {3}.Recurse on left subtree: root = 2 (last of {8,9,6,7,4,5,2}). In inorder {8,6,9,4,7,2,5}, 2 appears at position 6. Left subtree inorder = {8,6,9,4,7}, right = {5}.Recurse: root = 4 (last of postorder {8,9,6,7,4}). In inorder {8,6,9,4,7}, 4 appears at position 4. Left = {8,6,9}, right = {7}.Recurse: root = 6 (last of {8,9,6}). In inorder {8,6,9}, 6 is at position 2. Left = {8}, right = {9}.Nodes 8 and 9 are leaves (depth 4 from root 1). The path 1→2→4→6→8 has 4 edges, so height = 4.Key Concept: A binary tree can be uniquely reconstructed from its inorder and postorder traversals. The last element of postorder is always the root. Finding the root in the inorder sequence divides the remaining elements into left and right subtrees. Repeating this recursively rebuilds the entire tree. The height is the number of edges on the longest root-to-leaf path.

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 the binary tree is _______.(Height = length of longest path from root to any leaf, measured in number of edges)

Master GATE-CS with Our Test Series

More Questions from Trees and Binary Trees

Frequently Asked Questions

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 the binary tree is _______.(Height = length of longest path from root to any leaf, measured in number of edges)

Master GATE-CS with Our Test Series

More Questions from Trees and Binary Trees

Frequently Asked Questions