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
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
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Karnataka INDIA.