First time here? Checkout the FAQ!
+3 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


asked in DS by Veteran (53.1k points)   | 97 views
Not able to understand how the above program is related to options.. ??,
Ans given B)

very nice refreshing question ...  (y)..

the question is using Logic of BST. where at each node, left is less than node and right is greater than the node ( data).

Now ...understand the above-given program..where the input is preorder of BST, and count of total no of nodes in the BST. Now the program is traversing the pre-order from the end and first, it is checking elements .. either it should less than the prev. min or greater than the prev. the concept lies here with BST... if any node has two children then its value must be lying between its left child data and right child data ...right ?? so ..when we will be traversing this particular node in the loop then it will return 0 ...because it will neither satisfy if(a[i] < min) nor it will satisfy - else if (a[i] > max ) ..and will go in the else block and will return 0..

hence... option B is correct. now work on different BST will get the clear ..concept.


one more point to be noted here is - Pre-order traversal contains root node before its both child and hence during traversal of that pre-order from back end will see child first and then will see parent node..and when it will rach to a node ( parent node) with two child, it would be neither less than the prev min nor greater than prev. max..and at that point it will return 0... 

If its an in order traversal instead of pre-order then for any BST tree, the given program would always return 1, because inorder traversal gives sorted list. And now see the above program where program will always satisfy-  if(a[i] <min) and finally will return 1.

If its a post-order, then also it will return 1 always for all BST... ... now do it by your own..


You can make both the comments as answer !!

2 Answers

+3 votes
Best answer

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

answered by Veteran (24.7k points)  
selected by
is the code is searching from last to first?

how do u know?

size in the code = total no of nodes. ( data).

a[size -1]  -> last node

a[size-2]  -> 2nd last node.

max= max( a[size-1] , a[size-2]).

min= min( a[size-1] , a[size-2])

for( i = size -3 ( 3rd last node) ; i>=0 ( run till first node) ; i-- ).


0 votes

Option B.


answered by Active (1.2k points)  

Related questions

0 votes
0 answers
asked in DS by Vishal Goyal Junior (949 points)   | 40 views
0 votes
0 answers
asked in DS by Vishal Goyal Junior (949 points)   | 42 views

Top Users Apr 2017
  1. akash.dinkar12

    3782 Points

  2. Divya Bharti

    2696 Points

  3. Deepthi_ts

    2270 Points

  4. rude

    2142 Points

  5. Tesla!

    1888 Points

  6. Sanjay Sharma

    1692 Points

  7. Debashish Deka

    1668 Points

  8. Shubham Sharma 2

    1610 Points

  9. Prashant.

    1580 Points

  10. Arjun

    1570 Points

Monthly Topper: Rs. 500 gift card

22,135 questions
28,125 answers
24,261 users