GATE Exam > GATE Questions > The postorder traversal of a binary tree is 8...
Start Learning for Free
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 ______.
Correct answer is '4'. Can you explain this answer?
| FREE This question is part of | Download PDF Attempt this Test |
Verified Answer
The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The ino...
Given, post-order – 8, 9, 6, 7, 4, 5, 2, 3, 1
and in-order – 8, 6, 9, 4, 7, 2, 5, 1, 3
and in-order – 8, 6, 9, 4, 7, 2, 5, 1, 3
Construct a binary tree from postorder and inorder traversal :
The height of the binary tree above is 4.
Most Upvoted Answer
The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The ino...
Solution:
The postorder traversal of a binary tree is obtained by visiting the nodes in the order: left, right, root. Similarly, inorder traversal is obtained by visiting the nodes in the order: left, root, right.
Let's use this information to construct the binary tree for the given postorder and inorder traversals.
1. Find the root of the binary tree
- From postorder traversal, we know that the last element is the root of the tree. Hence, the root of this binary tree is 1.
2. Find the left and right subtrees of the root
- From inorder traversal, we can see that the elements to the left of the root 1 belong to the left subtree, and the elements to the right belong to the right subtree.
- Hence, the left subtree has elements: 8,6,9,4,7; and the right subtree has elements: 2,5,3.
3. Repeat steps 1 and 2 for the left and right subtrees
- For the left subtree, the last element in the postorder traversal is 7, which is the root of the left subtree. The left and right subtrees of 7 can be obtained from the elements to the left and right of 7 in the inorder traversal.
- Similarly, for the right subtree, the last element in the postorder traversal is 3, which is the root of the right subtree. The left and right subtrees of 3 can be obtained from the elements to the left and right of 3 in the inorder traversal.
Using this process, we can construct the following binary tree:
```
1
/ \
/ \
/ \
8 2
/ \ / \
6 9 5 3
/ \
4 7
```
The height of a binary tree is the length of the longest path from the root to any leaf. In this case, the longest path is from the root 1 to the leaf node 4, which has a height of 4 edges.
Hence, the height of the binary tree is 4.
The postorder traversal of a binary tree is obtained by visiting the nodes in the order: left, right, root. Similarly, inorder traversal is obtained by visiting the nodes in the order: left, root, right.
Let's use this information to construct the binary tree for the given postorder and inorder traversals.
1. Find the root of the binary tree
- From postorder traversal, we know that the last element is the root of the tree. Hence, the root of this binary tree is 1.
2. Find the left and right subtrees of the root
- From inorder traversal, we can see that the elements to the left of the root 1 belong to the left subtree, and the elements to the right belong to the right subtree.
- Hence, the left subtree has elements: 8,6,9,4,7; and the right subtree has elements: 2,5,3.
3. Repeat steps 1 and 2 for the left and right subtrees
- For the left subtree, the last element in the postorder traversal is 7, which is the root of the left subtree. The left and right subtrees of 7 can be obtained from the elements to the left and right of 7 in the inorder traversal.
- Similarly, for the right subtree, the last element in the postorder traversal is 3, which is the root of the right subtree. The left and right subtrees of 3 can be obtained from the elements to the left and right of 3 in the inorder traversal.
Using this process, we can construct the following binary tree:
```
1
/ \
/ \
/ \
8 2
/ \ / \
6 9 5 3
/ \
4 7
```
The height of a binary tree is the length of the longest path from the root to any leaf. In this case, the longest path is from the root 1 to the leaf node 4, which has a height of 4 edges.
Hence, the height of the binary tree is 4.
|
Explore Courses for GATE exam
|
|
Similar GATE Doubts
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 ______.Correct answer is '4'. Can you explain this answer?
Question Description
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 ______.Correct answer is '4'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about 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 ______.Correct answer is '4'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for 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 ______.Correct answer is '4'. Can you explain this answer?.
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 ______.Correct answer is '4'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about 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 ______.Correct answer is '4'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for 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 ______.Correct answer is '4'. Can you explain this answer?.
Solutions for 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 ______.Correct answer is '4'. Can you explain this answer? in English & in Hindi are available as part of our courses for GATE.
Download more important topics, notes, lectures and mock test series for GATE Exam by signing up for free.
Here you can find the meaning of 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 ______.Correct answer is '4'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
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 ______.Correct answer is '4'. Can you explain this answer?, a detailed solution for 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 ______.Correct answer is '4'. Can you explain this answer? has been provided alongside types of 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 ______.Correct answer is '4'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice 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 ______.Correct answer is '4'. Can you explain this answer? tests, examples and also practice GATE tests.
|
|
Explore Courses for GATE exam
|
|
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
Follow Us
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup