A binary search tree contains the value $1, 2, 3, 4, 5, 6, 7, 8$. The tree is traversed in pre-order and the values are printed out. Which of the following sequences is a valid output?
Note: PreOrder means Root-Left-Right Traversal of tree.
By Option Elimination:-
B. False. Because $5$ is root so in preorder sequence first $5$ elements must contain $1$ to $5$ But $6$ comes here. So false.
So, now common things in option A,C,D is $5,3$ means $5$ root then LHS subtree root is $3$ . now $3$ s LHS is $1,2$ so they should come first rather than $4$. So option C is False.
Now Check for Option A,D.
Root $5$'s RHS is $6,7,8$ now as per Option A,D $7$ is Root so $6$ should be Left and $8$ should be Right so pre order for Right sub tree is $7,6,8$ (Root-L-R). This satisfies option D.
Correct Answer: $D$
@Rajesh Pradhan Thank You so much for explaining such nice approach.
I'm able to make tree for option (b) also. Please guide me where am I heading wrong!
if you find preorder of tree you have drawn it will be 5 3 1 2 4 6 7 8
but should be show 5 3 1 2 6 4 7 8 so you have done mistake
The tree is:
can u please explain how did u make this tree? in which sequence have you taken the data..
for example if a sequence is 1,2,3,4,5,6,7,8
then tree would be like:-
1 2(right child of 1), 3(right child of 2), 4(right child of 3) and so on...
how did you draw the above tree isnt it wrong?
try here https://www.cs.usfca.edu/~galles/visualization/AVLtree.html