KEMBAR78
1-Create An Integer Function IsBST | PDF | Teaching Methods & Materials | Science & Mathematics
Scribd
Upload
8 views1 page

1-Create An Integer Function IsBST

The document describes how to write a function that checks if a binary tree is a binary search tree. It explains initializing a static pointer, recursively checking the left and right subtrees, and checking that nodes are in the correct order compared to the previous node.

Uploaded by

Jaykishor Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
8 views1 page

1-Create An Integer Function IsBST

The document describes how to write a function that checks if a binary tree is a binary search tree. It explains initializing a static pointer, recursively checking the left and right subtrees, and checking that nodes are in the correct order compared to the previous node.

Uploaded by

Jaykishor Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 1

1-Create an integer function isBST and pass the pointer to the root node of the

tree you want to check as the only parameter. Inside the function, check if the
pointer is not NULL, as we have been checking the whole time, and this is also
considered as the base case for the recursion to stop. If it is NULL, we would
simply return 1 since an empty tree is always a binary search tree. Else, this is a
complex yet understandable part. You should follow what I am saying.

2-Create a static struct Node pointer prev initialised with NULL. This maintains
the pointer to the parent node. And since the root node doesn't have any parent, we
have initialized it with NULL and made it static.

3-Now, see if the left subtree is a Binary Search Tree or not, by calling it
recursively. If it is not a BST, return 0 here itself. Else, see if the prev is not
NULL otherwise this is the root node of the whole tree and we won't check this
condition. If the prev node is not NULL and the current node, which is the root
node of the current subtree, is smaller than or equal to the prev node, then we
would return 0. Since this violates the increasing orderliness.

4-If it still passes all the if conditions we have structured above, we will store
the current node in the prev and move it recursively to the right subtree. And this
is nothing but a modified version of the InOrder Traversal.

5- int isBST(struct node* root){


static struct node *prev = NULL;
if(root!=NULL){
if(!isBST(root->left)){
return 0;
}
if(prev!=NULL && root->data <= prev->data){
return 0;
}
prev = root;
return isBST(root->right);
}
else{
return 1;
}
}

You might also like