Find out if the given tree is BST or
not
If
we just check the root, left, right property of every node, and all
of them are BSTs in themselves, we cannot say the resulting tree is
also BST. For example:
5
/ \
3 7
\
9
In
the above, 3 < 5 < 7 (BST is complete for root and its
immediate children).
Subtrees
(involving node and their immediate children) at 3, 9 and 7 are all
BSTs
Yet
the whole tree is not BST because 9 lies in left subtree of 5
This
indicates, that the test for BST should check to see that all the
nodes lying left to a node should be smaller than that node and the
nodes to the right of a node should all be greater than that node.
Due
to the above property, every node should lie in a range defined by
its closest right and left parents.
// Call the below as:
// isBST (root, INT_MIN, INT_MAX);
int isBST(TreeNode node, int min, int max)
{
if (node==NULL)
return 1;
if (node.data < min || node.data > max)
return 0;
return
isBST(node.left, min, node.data-1) &&
isBST(node.right, node.data+1, max);
}
Solution
2: Another
solution is to traverse the tree in In-Order.
If
the tree is BST, then in-order traversal should print a sorted
output.
If
we store previous in-order node and compare with current node, we can
have check BST
bool isBST(TreeNode root)
{
static TreeNode prev = NULL;
if (root)
{
if (!isBST(root.left))
return false;
if (prev != NULL && root.data <= prev.data)
return false;
prev = root;
return isBST(root.right);
}
return true;
}
|