Register

Can we generate a unique Binary tree with Post Order and Level Order traversal. Explain?

3,623 views

2 Answers

Best answer
12 votes
12 votes

Its not Possible for Post order and Level Order.

Consider the above graph:

Following combination can uniquely identify a tree.

Inorder and Preorder.
Inorder and Postorder.
Inorder and Level-order.

And following do not.
Postorder and Preorder.
Preorder and Level-order.
Postorder and Level-order.

For example, Preorder, Level-order and Postorder traversals are same for the trees given in above diagram.

Preorder Traversal = AB
Postorder Traversal = BA
Level-Order Traversal = AB

So, even if three of them (Pre, Post and Level) are given, the tree can not be constructed.

• selected by
User Avatar
2 votes
2 votes
No a unique binary tree cannot be constructed. It is a necessary condition tat Inorder Traversal be given along with any of the other traversals as well.

Other than this if any other traversal is given it'll not be possible to construct a binary tree.

Hope it helps!!!. :)

http://www.geeksforgeeks.org/if-you-are-given-two-traversal-sequences-can-you-construct-the-binary-tree/
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
2 answers
2
gshivam63 asked May 31, 2016
2,941 views
Post order traversal
Post order traversal of a BST is 35,50,55,60,50,100.then what can you say about the tree? (A) Min heap (B) Max heap (C) Strict binary tree (D) None of these
Post order traversal of a BST is 35,50,55,60,50,100.then what can you say about the tree?(A) Min heap(B) Max heap(C) Strict binary tree(D) None of these
User Avatar
4 votes
4 votes
1 answer
4
Shashank Chavan asked Jan 18, 2016
11,247 views
What's the difference between Binary tree height, level and depth?
What's the difference between Binary tree height, level and depth? Sometimes it's confusing! Does there definition change according to question also, if mentioned?
What's the difference between Binary tree height, level and depth? Sometimes it's confusing!Does there definition change according to question also, if mentioned?
User Avatar
Link Copied!