DS-BST

Question

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

Comments

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. max...now 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 ..you 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 ..it 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..

---

@vijaycs

You can make both the comments as answer !!

Answer 1

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

Comments

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

??

Answer 2

Option B.