4 votes 4 votes Suppose binary tree has only three nodes A,B and C, and you are given the post order traversal of tree as B-A-C . The exact pre order traversal of the tree is? A)C-A-B B)A-B-C C)C-B-A D)Can't be determined from given information. DS gateforum-test-series data-structures binary-tree + – Parth Shah asked Dec 11, 2018 recategorized Mar 14, 2019 by ajaysoni1924 Parth Shah 1.4k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Lakshman Bhaiya commented Dec 11, 2018 i edited by Lakshman Bhaiya Dec 11, 2018 reply Follow Share $(D)$ is the correct 0 votes 0 votes Gupta731 commented Dec 11, 2018 reply Follow Share C.. 0 votes 0 votes parabol commented Dec 11, 2018 reply Follow Share I think answer is 'D' ,there are different configuration of trees with that postorder, which have different preorder. (Generally,a binary tree could be only reconstructed only if inorder is given along with postorder or preorder) See the figure 2 votes 2 votes Shaik Masthan commented Dec 11, 2018 reply Follow Share this may help you to understand the concept https://gateoverflow.in/268182/%23doubt 1 votes 1 votes Parth Shah commented Dec 11, 2018 reply Follow Share Thanks for the clarifications. So for BST if postorder is given then we can uniquely make the preorder for that BST whereas in a Binary tree there are possibilities that for given postorder we can get multiple preorders. Right? 0 votes 0 votes parabol commented Dec 11, 2018 reply Follow Share Yes, In BST , inorder traversal is always in the ascending order of elements. If postorder or preorder is given you can infer inorder as ascending order of elements without being explicitly specified. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes we can not determine ecectlly(uniqlly) what is preorder if postorder is given . we can see in the below binary tree we cant determine . abhishekmehta4u answered Mar 14, 2019 abhishekmehta4u comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes D. Can't be determined from the given info. The pre-order has 2 possibilities- C-A-B and C-B-A Ashish Goyal answered Dec 11, 2018 Ashish Goyal comment Share Follow See all 0 reply Please log in or register to add a comment.