DIR Return Create A Forum - Home
---------------------------------------------------------
techsuns
HTML https://techsuns.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: Puzzles && Algorithms
*****************************************************
#Post#: 311--------------------------------------------------
Determine if a Binary Tree is a Binary Search Tree.
By: srini Date: December 4, 2012, 3:11 am
---------------------------------------------------------
Write a function isBST(binarytree *node) to determine if a
Binary Tree is a Binary Search Tree.
#Post#: 312--------------------------------------------------
Re: Determine if a Binary Tree is a Binary Search Tree.
By: kranthipls Date: December 4, 2012, 3:16 am
---------------------------------------------------------
Are there any memory constraints???
#Post#: 316--------------------------------------------------
Re: Determine if a Binary Tree is a Binary Search Tree.
By: srini Date: December 4, 2012, 3:35 am
---------------------------------------------------------
First try for the naive algorithm(for the sake of forum
members), and then we go for O(1) space constraint. If you could
give both naive and efficient methods it would be helpful :D :D
: ::)
#Post#: 321--------------------------------------------------
Re: Determine if a Binary Tree is a Binary Search Tree.
By: kranthipls Date: December 4, 2012, 4:13 am
---------------------------------------------------------
Here is the pseudo code...
I did not write the is_sorted function which
trivial..............
[code]#include <stdio.h>
#define MAX_SIZE 1024
int inorder[MAX_SIZE];
int i = 0;
int main()
{
int result;
result = check_bst ( node);
if ( result == 1)
printf ("Yes it is a BST");
else
printf ("No it is not");
}
int check_bst (binarytree* node)
{
int array_size = do_inorder_traversal (node);
return is_sorted (inorder);
}
void do_inorder_traversal ( binarytree* node)
{
if ( node->left == NULL && node->right == NULL)
inorder[i++] = node -> element,return;
if ( node->left != NULL )
do_inorder_traversal ( node->left );
inorder[i++] = node -> element;
if ( node->right != NULL )
do_inorder_traversal ( node->right );
}
[/code]
#Post#: 324--------------------------------------------------
Re: Determine if a Binary Tree is a Binary Search Tree.
By: dinesh Date: December 4, 2012, 8:42 am
---------------------------------------------------------
For O(1) memory constraint, we can follow the approach taken in
the question given for the compilers CIE.
But we need 2 functions max and min which will return the max
and min values of all nodes below the given node. Then check if
the element in the node > max(node->left) and <
min(node->right). This procedure has to be done for all nodes in
the tree.
#Post#: 327--------------------------------------------------
Re: Determine if a Binary Tree is a Binary Search Tree.
By: srini Date: December 4, 2012, 10:03 am
---------------------------------------------------------
For O(1) space constraint:
Since we are doing in-order traversal of binary tree, the
previous node's value is always less than the current node's
value.
#Post#: 333--------------------------------------------------
Re: Determine if a Binary Tree is a Binary Search Tree.
By: satya Date: December 4, 2012, 10:35 pm
---------------------------------------------------------
how are u ensured that previous node's value is less than the
current node's value. It may not be binary search tree right??
#Post#: 352--------------------------------------------------
Re: Determine if a Binary Tree is a Binary Search Tree.
By: srini Date: December 5, 2012, 9:07 am
---------------------------------------------------------
If the above mentioned condition fails then it is not binary
search tree, which is what we trying to determine :o
Can you post the psedo code?
*****************************************************