1 votes 1 votes Given a preorder, postorder and inorder traversal of a tree, is it always possible to obtain a tree that satisfies each of the three conditions? Or is it possible to not obtain a tree at all? DS binary-tree algorithms spanning-tree binary-search-tree + – Parimal Paritosh asked Feb 19, 2018 Parimal Paritosh 1.2k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes To clarify your doubt i'hv taken exmaple. Parimal Paritosh. gari answered Feb 25, 2018 gari comment Share Follow See 1 comment See all 1 1 comment reply smsubham commented Feb 28, 2018 i edited by smsubham Jun 4, 2018 reply Follow Share Exactly. When no tree is possible obviously we cannot obtain it. But if we are given a valid sequence of the three, we can always uniquely determine the corresponding tree. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Given any of below order traversal you will able to identify tree.. (Inorder and Preorder) OR (Inorder and Level-order) OR (Inorder and Postorder) Tarun kushwaha 1 answered Feb 19, 2018 Tarun kushwaha 1 comment Share Follow See all 4 Comments See all 4 4 Comments reply Parimal Paritosh commented Feb 19, 2018 reply Follow Share I tried drawing a tree for Inorder ABC, preorder BAC, postorder CAB. But I couldn't find such a tree. Can you help me in drawing it? 0 votes 0 votes Tarun kushwaha 1 commented Feb 19, 2018 reply Follow Share It is not always possible to satisfy all three at a time ,given any two of above we can create unique tree. 1 votes 1 votes smsubham commented Feb 28, 2018 reply Follow Share @ Parimal Paritosh There is something called GIGO (Garbage In Garbage Out). When you give invalid traversal of the tree then how can you expect to get the correct output? I don't think it is a valid traversal, so we cannot get unique (valid tree) , as no such tree exists. 0 votes 0 votes ravi kant Gautam commented Apr 27, 2018 reply Follow Share @ parimal paritosh We can't find unique tree always taking preorder and postorder but when we take inorder in combination then we can find unique tree. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes There is always a unique tree which satisfies all the three conditions. himgta answered Feb 19, 2018 himgta comment Share Follow See 1 comment See all 1 1 comment reply Parimal Paritosh commented Feb 19, 2018 reply Follow Share I tried drawing a tree for Inorder ABC, preorder BAC, postorder CAB. But I couldn't find such a tree. Can you help me in drawing it? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes We know that given post-order and in-order or pre-order and in-order we can uniquely construct a binary tree. But it might be possible that given any arbitrary sequences, it is not necessary that there is a binary tree corresponding to that, just like in the example given by you. There exists no binary tree which will satisfy the given post-order and in-order simultaneously. You may refer to this nptel lecture (at time 35:04) https://www.youtube.com/watch?v=eWeqqVpgNPg&list=PLBF3763AF2E1C572F&index=7 SameekshaGupta answered Feb 25, 2018 SameekshaGupta comment Share Follow See all 0 reply Please log in or register to add a comment.