C-program to check whether a binary tree is a Binary search tree
Posted: Sat, 22 Dec 2007 06:02:00 -0600
8. Write a C program to check if a given binary tree is a binary search tree or not?
Solution:
If the given binary tree is a Binary search tree,then the inorder traversal should output the elements in increasing order.We make use of this property of inorder traversal to check whether the given binary tree is a BST or not.We make note of the latest element that could have been printed and compare it with the current element.Given below is a C function to check it.
bool flag=true;
void inorder(tree T,int *lastprinted)
{
if(T==NULL)
{
printf("the tree is empty .Hence, it is a BST\n");
}
else
{
if(T->left!=NULL)
{
inorder(T->left,lastprinted);
}
if(T->data > *lastprinted)
{
*lastprinted=T->data;
}
else
{
printf("the given binary tree is not a BST\n");
flag=false;
exit(0);
}
inorder(T->right,lastprinted);
}
}
Now check the value of flag to say whether it is a BST or not.If it is not then it is already taken care by the code.
C-program to make a copy of a tree
7.Write a C program to create
a copy of a tree
Solution:
#include<stdio.h>
struct binarysearchtree{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;
tree copy(tree T)
{
if(T== NULL)
return NULL;
else
{
tree *newtree=(tree*)malloc(sizeof(tree));
newtree->data=tree->data;
newtree->left=copy(T->left);
newtree->right=copy(T->right);
return newtree;
}
}
