## Friday, February 18, 2011

### Construct binary tree using Post-order and Pre-order Traversals

Is it possible to build a binary tree given only Post-order and Pre-order traversals of that tree?

Subscribe to:
Post Comments (Atom)

skip to main |
skip to sidebar
## Friday, February 18, 2011

###
Construct binary tree using Post-order and Pre-order Traversals

## About Me

## Labels

Is it possible to build a binary tree given only Post-order and Pre-order traversals of that tree?

Subscribe to:
Post Comments (Atom)

- Bhavin Shah
- People who know me, know me...others why bother, enjoy a good read and post healthy comments :-)

Viraj Turakhia - ofcourse it is not possible with just one tree traversal.. that is, unique tree contruction

ReplyDeleteit is not even possible with two traversals in some cases

for example:

post-order: aaaaaaaa

pre-order: aaaaaaaa

go construct a unique tree

Bhavin Shah - @Vraj

1. lets assume input does not contain duplicate

2. jsut to clarify, I always meant both post-order and pre-order are given

Viraj Turakhia - w/o duplicates, it should be possible to construct unique tree with any two traversals.

don't ask for algo.. can't write it here

Bhavin Shah - nope its not possible if you have just post-order and pre-order traversals of binary tree.

consider following input:

pre-order: ab

post-order: ba

you need two traversals and one of them has to be in-order.

Viraj Turakhia - a is root and b is the only child.. tht's unique representation.. why u think it is not possible?

Bhavin Shah - which child...left or right?

Viraj Turakhia - thts non-deterministic even wen u draw this tree on paper.. :)

Bhavin Shah - @Sagar told me both of them are correct answers.

I differ on it, I think there could be only one correct answer so with the available information we can get only this far and we need more information to proceed.

Can we construct a tree by the postorder txyCabDBA

ReplyDeleteWhere small letters are leaf node

ReplyDeleteCapital letters are intermediate and root node