top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

How to find if given binary tree is binary search tree?

+4 votes
939 views
How to find if given binary tree is binary search tree?
posted Oct 30, 2013 by Majula Joshi

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
Do in order traversal if next element  is more then previous then its a Binary Search Tree.
Not fully sure. If in-order traversal of tree is ordered monotonically it should be binary search tree.
In order should give only sorted output for the BST.

1 Answer

+1 vote

Pseudo Code is something like this -

current = -infinite;

inorder(node, treeType)
{
   if node == null then return;

   inorder(node->left, treeType);
   if current >= node->data then treeType = "No BST"

   current = node-> data;
   inorder(node->right, treeType);
}

Call the function something like

inorder(head, "BST");
answer Oct 30, 2013 by Salil Agrawal
...