CODEWITHSUNDEEP
ctreebinary-search-tree
vatsal
vatsal

Reputation: 49

Why output of my BST-validating function is false?

I wrote a function to populate a BST and another one to verify a given tree is a valid BST.

I could not understand why my check function returns false, since I have created the input as a BST.

When I pass a tree through my check function it checks four things:

  1. First it checks that if the data in the left child is smaller than the data in the present child;
  2. It checks that data in the right side is greater than the data in the present child;
  3. Then it passes the address of left child as the root for the next operation where it will do same for the left child (now passed as root): here it will again check if the root (now root, previously left child) has a left child that is smaller than the present node and the right side greater similarly.
  4. We pass the right side address as node, so that we can check if it's left side is smaller and the right side is bigger.

...and after all these operations return, we get true (if valid) else false.

It should return me true, however the output is false and I could not understand why?

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct tree{
    int data;
    struct tree* left;
    struct tree* right;
};

struct tree* push(int d,struct tree*head1) {
    if(head1==NULL){
        head1=(struct tree*) malloc(sizeof(struct tree));
        head1->data=d;
        head1->left=head1->right=NULL;
        return head1;
    }
    else if(head1->data>d){;
        head1->right=push(d,head1->right);
    }
    else{
        head1->left=push(d,head1->left);
    }
    return head1;
}

bool small(struct tree* a,int b){
    if(a==NULL){return true;}
    if(a->data<b){return true;}
    else {return false;}
}

bool large(struct tree* a,int b){
    if(a==NULL){return true;}
    if(a->data>b ){return true;}
    else {return false;}
}

bool check(struct tree*head ){
    if(head==NULL){
        printf("empty\n");
        return true;
    }
    printf("2");
    if(small(head->left,head->data)&& large(head->right,head->data) && check(head->left) && check(head->right)){
        printf("true");
        return true;
    }
    else {
        printf("false\n");
        return false;
    }
}

int main(){
    struct tree*head;
    head=push(3,head);
    head=push(10,head);
    head=push(5,head);
    check(head);
    // printf("%d",head->data);
    return 0;
}

Upvotes: 0

Views: 60

Answers (2)

trincot
trincot

Reputation: 350781

Besides the missing initialisation of head, the main cause for the problem mentioned in your question is in your push function:

  • It goes into the wrong side for the recursive call. The comparison with d should be the opposite:

         else if(head1->data < d){  // Fix comparison

But there is also a mistake that we can even see in the description of your algorithm: to verify a BST you should not only verify that the left child's data is less, and the right child's data is more. You should verify that all nodes in the left side subtree have values that are less, and all nodes in the right side subtree have values that are more.

This you have not implemented, and so you will get false positives, like for this tree, which is not a BST:

             5
           /
          1
            \
             10

Here is one way to do it correctly:

#include <limits.h>

// Helper function: arguments define a "window" for the (sub)tree
bool checkWindow(struct tree*head, int low, int high) {
    return head == NULL 
           || low <= head->data  && head->data <= high
               && checkWindow(head->left, low, head->data)
               && checkWindow(head->right, head->data, high);
}

bool check(struct tree*head ){
    return checkWindow(head, INT_MIN, INT_MAX);
}

Upvotes: 1

Weather Vane
Weather Vane

Reputation: 34585

In function main() you have

struct tree*head;
head=push(3,head);

but the compiler objects to you passing an uninitialised variable.

In the push() function you have

if(head1==NULL)

but that is useless, since the value of head1 is indeterminate. in main() you should have

struct tree *head = NULL;
head = push(3, head);

but there may still be other problems.

Upvotes: 0

Related Questions