48 votes 48 votes Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited `in a postorder, inorder and preorder traversal respectively, of a complete binary tree. Which of the following is always true? LASTIN = LASTPOST LASTIN = LASTPRE LASTPRE = LASTPOST None of the above DS gatecse-2000 data-structures binary-tree normal + – Kathleen asked Sep 14, 2014 recategorized Jun 30, 2017 by Silpa Kathleen 17.5k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments stblue commented Jan 11, 2018 reply Follow Share @vishalsharma539 Complete Binary tree : A binary tree is complete if all level except possibly the last level is completely full, i.e last level may be or may not be full. Perfect Binary tree : A complete binary tree in which last level is full. Almost complete binary tree : A almost complete binary tree is a binary tree which is complete binary tree but not perfect binary tree. 0 votes 0 votes Lakshman Bhaiya commented Oct 26, 2018 reply Follow Share I do not understand what is the meaning of Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited `in a postorder, inorder and preorder traversal respectively?? 2 votes 2 votes srestha commented Aug 23, 2019 i edited by srestha Aug 23, 2019 reply Follow Share @Lakshman Patel RJIT It is nothing but just simple preorder, postorder, inorder traversal. 0 votes 0 votes Please log in or register to add a comment.
Best answer 70 votes 70 votes Inorder : Left $\rightarrow$ Root $\rightarrow$ Right Preorder : Root $\rightarrow$ Left $\rightarrow$ Right Postorder: Left $\rightarrow$ Right $\rightarrow$ Root If the binary tree is full (last level is fully filled), the last visited node in Inorder and Preorder must be the rightmost one in the last level. But for a complete binary tree this need not be the case (in a complete binary tree last level need not be fully filled) and LASTPRE will be from the second last level in case the complete binary tree is not full. So, choice (D). Arjun answered Dec 14, 2014 edited Dec 24, 2017 by kenzou Arjun comment Share Follow See all 17 Comments See all 17 17 Comments reply Gate Keeda commented Dec 14, 2014 reply Follow Share I guess this is also a Complete Binary Tree. And the question has asked for the condition which is always true. In some cases what you said may not be true as the above one. 70 votes 70 votes Danish commented Dec 14, 2014 reply Follow Share yeah right thanks !!! 2 votes 2 votes Arjun commented Dec 15, 2014 reply Follow Share Yes. You are correct. I took "full" instead of "complete". 6 votes 6 votes Saurabh Sharma commented Aug 13, 2015 reply Follow Share Arjun Sir, Can you please explain the difference between full and complete binary tree as different sources have different binary trees 2 votes 2 votes Akash Kanase commented Nov 23, 2015 reply Follow Share Please update this answer. 5 votes 5 votes Vijay Thakur commented Aug 22, 2016 reply Follow Share This is copied from Rosen, and the defiition of complete Binary Tree is different than yours. the tree which you are calling as Full is same as Complete tree. answer should be (B), right? 3 votes 3 votes ravi_ssj4 commented Sep 6, 2016 reply Follow Share As far as I know, if the definition is not mentioned, then a complete binary tree is one in which nodes are present sequentially(i.e. following the property of Almost Complete Binary tree) and a node can have either 0 or 2 children. A node should'nt have just a single child thus !! 1 votes 1 votes nitish commented Nov 26, 2016 reply Follow Share @Arjun sir Can you please share an example of this question. Because below tree is Not Complete Binary Tree ; it is almost Complete Binary tree. https://gateoverflow.in/?qa=blob&qa_blobid=6157632728430700751 0 votes 0 votes sushmita commented Jan 25, 2017 reply Follow Share A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. This is 100% correct. 13 votes 13 votes rahul sharma 5 commented Oct 3, 2017 reply Follow Share @Arjun sir,In answer you mentioned that :- LASTPRE will be from the second last level in case the complete binary tree is not full. So, choice (D). LastIn should be from second lastindex in case last level is completely filled.LASTPRE will always be from last level.because if we are at second last level we process ROOT and then goto last level in pre order.Please check once? 2 votes 2 votes Shubham Aggarwal commented Aug 29, 2018 reply Follow Share This tree is almost complete binary tree because almost complete binary tree means leave should be present at last level and last but one level. 0 votes 0 votes Abhisek Tiwari 4 commented Oct 11, 2018 reply Follow Share Will it 'B' for full binary Tree? 0 votes 0 votes anchitjindal07 commented Dec 27, 2018 reply Follow Share @Arjun Sir please give example.. I think what u explained is true for Almost Complete Binary tree and not for complete binary tree. As per me, the answer to this question is same for Complete Binary Tree and Full Binary Tree 0 votes 0 votes Kuljeet Shan commented Mar 2, 2019 i edited by Kuljeet Shan Mar 4, 2019 reply Follow Share @Gate Keeda @rahul sharma 5 @sushmita According to book of DS by Thomas H. Cormen For complete Binary tree all levels should contain maximum nodes and in if in last level nodes are available from left to right that is called Nearly Completely Binary tree. In question it is mentioned as complete binary tree. So, isn't option (B) seems to be correct ? 0 votes 0 votes Kiyoshi commented Apr 26, 2021 reply Follow Share @Abhisek Tiwari Will it 'B' for full binary Tree? Yes, absolutely why it can’t be... because every time you make the inorder and preorder traversal you will get the … LASTIN = LASTPRE 1 votes 1 votes deb_141 commented Mar 22, 2022 i edited by Abhrajyoti00 Nov 5, 2022 reply Follow Share @Gate Keeda I think that depends. E.g. if you take this complete binary tree, then you'll get both LASTIN and LASTPRE as 7. So taking an examples is probably not the best way to address this question. 1 votes 1 votes theradash commented Nov 8, 2023 reply Follow Share @Arjun sir, I believe you mean to say LASTIN will be from second last level.As in that case LASTPRE will from last and LASTIN from second last. 0 votes 0 votes Please log in or register to add a comment.
22 votes 22 votes The answer is D. Take any random sequence and check for the inorder, postorder and preorder Last Node. Gate Keeda answered Dec 8, 2014 Gate Keeda comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments Ayush Upadhyaya commented Dec 9, 2017 reply Follow Share Here, you have to be careful. It Says, "Complete binary tree" for which every level except last is completely filled and at last level, nodes are as far as left possible. 4 votes 4 votes Shubham Aggarwal commented Aug 29, 2018 reply Follow Share i am getting B as answer ..i take a perfect complete binary tree then the last of inorder and last of preorder is same. 0 votes 0 votes vishalshrm539 commented Aug 29, 2018 reply Follow Share @Shubham That will be same if the root contains both left and right child, but what if it doesn't ? Read above comment by Gate Keeda 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes REVERSE APPROACH !! Consider a Complete Binary Tree with only 1 node, say A, Then its PREORDER = POSTORDER = INORDER = A Therefore, only Option D matches (as Question ask, which always TRUE) Chandravardhan Singh answered Jan 1, 2022 Chandravardhan Singh comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes counter example for option B. Shatakshi_1 answered Sep 15, 2023 Shatakshi_1 comment Share Follow See all 0 reply Please log in or register to add a comment.