0 0 votes 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. Data Structures data-structures algorithms binary-search-tree binary-tree tree-traversal + – humblefool 2.1k views answer comment Share Follow Print See all 2 Comments 2 2 Comments reply Shubhanshu commented Nov 8, 2017 reply Follow flag 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 0 replyShare humblefool commented Nov 9, 2017 reply Follow flag 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 0 replyShare Please log in or register to add a comment.
2 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. raviyogi answered Nov 8, 2017 raviyogi comment Share Follow See all 5 Comments 5 5 Comments reply Show 2 previous comments humblefool commented Nov 10, 2017 reply Follow flag then why not in this case? here also inorder is given as well as a preorder ! But we cant find an unique tree !! 0 0 replyShare raviyogi commented Nov 10, 2017 reply Follow flag 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. 0 0 replyShare Lakshman Bhaiya commented Feb 2, 2018 i edited by Lakshman Bhaiya Feb 2, 2018 reply Follow flag It might help you 1 1 replyShare Please log in or register to add a comment.
