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 Show 14 previous comments 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 Danish commented Dec 14, 2014 reply Follow Share dont you think it should be (B) ? 5 votes 5 votes Gate Keeda commented Dec 14, 2014 reply Follow Share Look at my comment below for explanation. 0 votes 0 votes skrahul commented Dec 30, 2015 reply Follow Share always true for full binary tree ..but not for complete ! 2 votes 2 votes Rishi yadav commented Oct 4, 2017 reply Follow Share Yes for full binary tree it is option B 0 votes 0 votes 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.