Given a pre order, find whether it is single child BST

#include <stdio.h>
#include <limits.h>

int isSingleChildBST(int a[], int n){

int mx = INT_MAX, i;

for(i = 1; i < n ; ++i){

if(a[i] <= a[i - 1]){ //assuming equal elements are in left tree
mx = a[i - 1];
}else{
if(a[i] > mx)
return 0;
}
}

return 1;

}

int main(){

int a[] = {10,19,17,14,15,16};

printf("%s\n", isSingleChildBST(a, 6) ? "YES" : "NO");
return 0;
}
Advertisements

6 thoughts on “Given a pre order, find whether it is single child BST

  1. why that assumption ??we should not take it into consideration(i.e it is valid for only some cases) right??ex: preorder: 5 3 2 4 7 8it is giving wrong even not visiting the right side of root how??

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s