CODEWITHSUNDEEP
binary-treetraversal
shardul08
shardul08

Reputation: 101

Given postorder traversal for a complete binary tree, find it's inorder traversal

If the given postorder traversal of the tree is BCA

then it's inorder traversal will be BAC

Is it possible to determine the inorder traversal just from the postorder traversal?

Upvotes: 0

Views: 96

Answers (1)

Syed Waris
Syed Waris

Reputation: 1074

It is not possible to find the inorder traversal, if only postorder traversal is given. Here is why:

    A          A                              A
   /            \                            / \
  C              C                          B   C
 /                \
B                  B

All have the postorder traversal as: BCA

But their inorder traversals are different. BCA, ACB and BAC respectively.

You need to have more constraint for a unique inorder traversal. If such a constraint is that the tree is complete, then it is possible to have a single inorder traversal.

Upvotes: 1

Related Questions