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 a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is ____

Answer 1

Answer:

Step-by-step explanation:

Answer 2

Answer:

4

Step-by-step explanation:

Postorder is (vertices 2, 4, 5, 6, 7, 8, 9), 3, 1

Inorder is     (vertices 2, 4, 5, 6, 7, 8, 9), 1, 3

Therefore:

• the part that is (vertices 2, 4, 5, 6, 7, 8, 9) is the left branch
• 1 is the root node
• 3 is the right branch

Left branch:

postorder is (vertices 4, 6, 7, 8, 9), 5, 2

inorder is     ( vertices 4, 6, 7, 8, 9), 2, 5

Therefore:

• the part that is (vertices 4, 6, 7, 8, 9) is the left branch
• 2 is the root node
• 5 is the right branch

Continuing, we get:

                  1

               /    \

             2      3

           /   \

        4      5

      /    \

    6      7

  /    \

8      9

The longest path is 1 - 2 - 4 - 6 - 8, which has length 4.

So the height of the tree is 4.