retagged by
12,123 views
22 votes
22 votes
The postorder traversal of a binary tree is $\text{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 _____
retagged by

3 Answers

Best answer
31 votes
31 votes



Nodes in longest path from Root to Leaf $= (1-2,2-4,4-6,6-8)\ or\ (1-2,2-4,4-6,6-9)$
$|\text{Longest Path}| = |(1-2,2-4,4-6,6-8)| = 4$

edited by
11 votes
11 votes

The systematic approach should be like this below. We know that

  • Post-order Traversal: $\mathrm{leftChild/SubTree}\rightarrow \mathrm{rightChild/SubTree}\rightarrow\mathrm{parent}$
  • In-order Traversal:     $\mathrm{leftChild/SubTree}\rightarrow\mathrm{parent}\rightarrow\mathrm{rightChild/SubTree}$

That's why we will remove at least the three nodes from the left side from both sequences in such a way that removed nodes satisfy the conditions above. It will discover the sub-tree containing the parent node as its root. Then put the parent node of that sub-tree to the sequence from the left. Repeating this process will yield the required binary tree.

$\left.\begin{matrix} (8, 9, 6), 7, 4, 5, 2, 3, 1\\ (8,6,9),4,7,2,5,1,3 \end{matrix}\right\}\Rightarrow 8-6-9 \Rightarrow 6$ is the parent node. 

 

 

$\left.\begin{matrix} (6, 7, 4), 5, 2, 3, 1\\ (6,4,7),2,5,1,3 \end{matrix}\right\}\Rightarrow 6-4-7 \Rightarrow 4$ is the parent node. 

 

 

 

 

$\left.\begin{matrix} (4, 5, 2), 3, 1\\ (4,2,5),1,3 \end{matrix}\right\}\Rightarrow 4-2-5 \Rightarrow 2$ is the parent node. 

 

 

$\left.\begin{matrix} (2, 3, 1)\\ (2,1,3) \end{matrix}\right\}\Rightarrow 2-1-3 \Rightarrow 1$ is the parent node.

 

 

 

Combining the sub-trees yield the required binary tree below.

 

So, the height of the tree is the length of the path of $~(1,2),(2,4),(4,6),(6,8)~$. Thus it is $4$.

 

0 votes
0 votes
5, i guess
Answer:

Related questions

32 votes
32 votes
6 answers
3
34 votes
34 votes
5 answers
4