The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
325 views
Given the preorder/postorder and inorder traversal of a binary tree, we can always construct a unique binary tree (I think so, correct me if I am wrong)

Construct a binary tree with the nodes A, B, C such that its preorder traversal is ABC and its inorder traversal is CAB.
asked in DS by Junior (993 points) | 325 views
0

Construct a binary tree with the nodes A, B, C such that its preorder traversal is ABC and its inorder traversal is CAB

such tree can't be constructed. 

0
So it means that given preorder/postorder and inorder, there is no guarantee that one can come up with a tree. But if one does come up with a tree, then it is guaranteed be unique, am I right?

1 Answer

+2 votes
unique tree can be generated

(preorder and inorder)=    yes

(postorder and inorder)=  yes

( preorder and postorder )=  no

 (inorder= cab and preorder=abc) => such tree dosnt exist.
answered by Active (2.6k points)
0
So it means that given preorder/postorder and inorder, there is no guarantee that one can come up with a tree. But if one does come up with a tree, then it is guaranteed be unique, am I right?
0
no, if inorder is given with any other traversal then tree will be constructed as well as unique.....
0
then why not in this case? here also inorder is given as well as a preorder ! But we cant find an unique tree !!
0
i this ques preorder and inorder given are not correct for any tree. and if they are correctly given we can create a unique tree.
+1

It might help you

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,240 questions
49,722 answers
163,928 comments
65,837 users