893 views
4 votes
4 votes

If preorder of a BST is passed as an argument to the above function. Function returns 1 if,

a)All the leaf nodes of the tree are at same level

b) All the nodes of the tree have atmost 1 child

c) True is a complete binary tree, where the nodes at each level are completely filled

d) None of these

2 Answers

Best answer
5 votes
5 votes

First of all, the above program is traversing the list from the end and checks whether any node is less than the prev. min or greater than the  prev. max ... if it lies between pev. min and prev. max then it returns 0.


Pre-Order traversal of BST - 

1. Root.

2. Left.

3. Right.

.So, Pre-order traversal of BST will contain elements like - root, ....., left,  ...., right ..  ... 

And we know that in a case of BST,   left < root < right. 


Now, if any node has two children then while traversing the pre-order from the back end, the program will return 0 when it will be traversing that particular node( with two children), because, before that point, we must have been traversed its both the left and right child. And since the current node element is neither less than prv. min ( if(a[i] < min) ----false)..nor it is greater than prev. max. ( else if (a[i] > max ----- false) and will go into else block and will return 0. 


Example - 

Pre-order - a [] = { 8, 3 , 1, 6 , 4 , 7 , 10 , 14, 13 }

now while trav. from back side-  max =14 , min =13

when we reach at node 6 ( which has two children). [ index =3 from start=0 ]. 
min =4 and max =14.

where 6 is neither less than the prev min = 4 nor greater than prev max = 14. Hence will return 0.


Example- 2- BST with at max 1 child to any node.

Pre- order traversal - a[ ] = { 10, 1, 9, 2, 7, 4].

Now traverse from back end-

max= 7, min=4.

now every time it will satisfy if(a[i] < min) and else if(a[i] > max) alternatively. Hence finally will return 1.


If it is Inorder instead of preorder - The above program would always return 1. [ inorder traversal gives sorted list.]

If it is postorder then also it will always return 1 for all BST. [ work on it ].

selected by

Related questions

1 votes
1 votes
2 answers
1
rahul sharma 5 asked Oct 6, 2017
780 views
What is the time complexity to delete the root node in right skew tree?I knew the three cases of BST deletion:- 0 child,one child,two child.But how can we handle this par...
2 votes
2 votes
1 answer
2
rahul sharma 5 asked Oct 2, 2017
440 views
What is the worst case time complexity to construct unique BST froma:) Inorder and preordera:) Inorder and postorder
1 votes
1 votes
1 answer
3
rahul sharma 5 asked Apr 12, 2018
667 views
a:) If given Tree is BST = Inorder of keys is sortedb:) Inorder of keys is sorted = Tree is BST(converse of above)I know first one holds.Is second one also true?If not ca...
0 votes
0 votes
1 answer
4