A weird situation while searching in a BST
While trying to make a function for traversal in a BST using the iterative approach, I came across this very confusive and dubious case, where the function is returning that it found the node with the specified key even when there is no node like that.
Below is the code of the same, and the problem is with the iterative BST searcher function of the name sBST_iter():-
#include <iostream>
using namespace std;
/* Program to practice on BST's */
typedef struct node{
int key;
struct node* left=NULL;
struct node* right=NULL;
int height;
} node;
int chkBst(node* root){
static node* prev=NULL;
if(root!=NULL){
if(!chkBst(root->left)){
return 0;
}
if(prev!=NULL and root->key<=prev->key){
return 0;
}
prev=root;
return chkBst(root->right);
}
else{
return 1;
}
}
node* searchBst_recur(node* root,int k){
if(root==NULL){
return NULL;
}
if(root->key==k){
return root;
}
if(root->key<k){
searchBst_recur(root->right,k);
}
else{
searchBst_recur(root->left,k);
}
}
node* sBst_iter(node* root,int k){
while(root!=NULL){
if(root->key=k){
return root;
}
else if(root->key<k){
root=root->right;
}
else{
root=root->left;
}
}
return NULL;
}
int main() {
node* root=(node*)malloc(sizeof(node));
node* a=(node*)malloc(sizeof(node));
node* b=(node*)malloc(sizeof(node));
node* c=(node*)malloc(sizeof(node));
node* d=(node*)malloc(sizeof(node));
node* e=(node*)malloc(sizeof(node));
node* f=(node*)malloc(sizeof(node));
node* g=(node*)malloc(sizeof(node));
root->key=12;
a->key=10;
b->key=15;
c->key=5;
d->key=11;
e->key=13;
f->key=17;
g->key=18;
root->left=a;
root->right=b;
a->left=c;
a->right=d;
b->left=e;
b->right=f;
f->right=g;
// Now this tree is a valid binary search tree, so let's see if our func gets this correct
int ans=chkBst(root);
// Getting a variable to store the ans returned from search funcs
node* ans1=NULL;
// The below recursive func works fine
// ans1=searchBst_recur(root,14);
cout<<"The tree is a BST: "<<ans<<endl;
/* This is the main problem---- */
ans1=sBst_iter(root,1);
// The above func should return NULL while searching for 1,
// but it returns 1 instead :(
if(ans1==NULL){
cout<<"Sorry!\n";
}else{
cout<<"The node got from searchBst_recur is "<<ans1->key<<endl;
}
return 0;
}
Comments
Post a Comment