top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

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

+4 votes
193 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 Google+ Share Button LinkedIn Share Button Multiple Social 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
Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...