27 votes 27 votes Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely? preorder and postorder inorder and postorder preorder and inorder level order and postorder I only II, III III only IV only DS gatecse-2004 data-structures binary-tree normal + – Kathleen asked Sep 18, 2014 Kathleen 8.7k views answer comment Share Follow See 1 comment See all 1 1 comment reply smsubham commented Dec 21, 2017 i edited by smsubham Dec 21, 2017 reply Follow Share To add Even if all Postorder, Preorder and Levelorder.are given tree cannot be uniquely determined. If we know the binary tree is full then we can construct even using preorder and postorder traversal. (not given in this question) See this https://www.geeksforgeeks.org/full-and-complete-binary-tree-from-given-preorder-and-postorder-traversals/ 16 votes 16 votes Please log in or register to add a comment.
Best answer 35 votes 35 votes 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. Answer: B shikharV answered Nov 15, 2015 edited Jun 13, 2018 by Milicevic3306 shikharV comment Share Follow See all 2 Comments See all 2 2 Comments reply talha hashim commented Aug 3, 2018 reply Follow Share even preorder, postorder and level order combinedly not identify uniqely 5 votes 5 votes Akash Papnai commented Nov 5, 2019 reply Follow Share Preorder and postorder can uniquely identify a tree but in one condition: The tree should be a Strict binary tree. (means each node should have zero or two children) 11 votes 11 votes Please log in or register to add a comment.
14 votes 14 votes Option b is correct i just draw a tree wrote the preorder,inorder,postorder,level order traversals I find out the options I and IV cant derive a unique tree. Bhagirathi answered Sep 21, 2014 Bhagirathi comment Share Follow See all 3 Comments See all 3 3 Comments reply Madhab commented Apr 15, 2016 i edited by Madhab Apr 15, 2016 reply Follow Share we can have more than 1 no of trees of same preorder and postorder so a tree uniquely can not be find using the preorder and post order traversal. 1 votes 1 votes Sachin Mittal 1 commented Jan 17, 2017 reply Follow Share even if three of them (Pre, Post and Level) are given, the tree can not be constructed. Inorder is must. http://www.cmi.ac.in/~madhavan/courses/programming06/lecture12-21sep2006.txt 17 votes 17 votes Shiva Sagar Rao commented Oct 12, 2020 reply Follow Share This is an archive of above link provided by @Sachin https://web.archive.org/web/20170530035959/https://www.cmi.ac.in/~madhavan/courses/programming06/lecture12-21sep2006.txt 2 votes 2 votes Please log in or register to add a comment.
3 votes 3 votes option B reference - https://math.stackexchange.com/questions/1531727/why-is-tree-not-uniquely-possible-with-given-preorder-and-postorder-traversal Rishi yadav answered Oct 5, 2017 Rishi yadav comment Share Follow See all 0 reply Please log in or register to add a comment.