recategorized by
17,496 views
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?

  1. LASTIN = LASTPOST
  2. LASTIN = LASTPRE
  3. LASTPRE = LASTPOST
  4. None of the above
recategorized by

4 Answers

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).

edited by
22 votes
22 votes
The answer is D.

Take any random sequence and check for the inorder, postorder and preorder Last Node.
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)

Answer:

Related questions

33 votes
33 votes
8 answers
1
Kathleen asked Sep 14, 2014
10,853 views
Consider the following nested representation of binary trees: $(X \ Y \ Z)$ indicates $Y$ and $Z$ are the left and right subtrees, respectively, of node $X$. Note that $Y...
55 votes
55 votes
8 answers
4
Kathleen asked Sep 14, 2014
9,737 views
An $n \times n$ array $v$ is defined as follows:$v\left[i,j\right] = i - j$ for all $i, j, i \leq n, 1 \leq j \leq n$The sum of the elements of the array $v$ is$0$$n-1$$n...