# Finding if a Binary Tree is a Binary Search Tree

Posted
by
dharam
on Stack Overflow
See other posts from Stack Overflow
or by dharam

Published on 2012-05-31T11:13:54Z
Indexed on
2012/06/10
4:40 UTC

Read the original article
Hit count: 418

Today I had an interview where I was asked to write a program which takes a Binary Tree and returns true if it is also a Binary Search Tree otherwise false.

My Approach1: Perform an inroder traversal and store the elements in O(n) time. Now scan through the array/list of elements and check if element at i^{th} index is greater than element at (i+1)^{th} index. If such a condition is encountered, return false and break out of the loop. (This takes O(n) time). At the end return true.

But this gentleman wanted me to provide an efficient solution. I tried but I was unsuccessfult, because to find if it is a BST I have to check each node.

Moreover he was pointing me to think over recusrion. My Approach 2: A BT is a BST if for any node N N->left is < N and N->right > N , and the INorder successor of left node of N is less than N and the inorder successor of right node of N is greater than N and the left and right subtrees are BSTs.

But this is going to be complicated and running time doesn't seem to be good. Please help if you know any optimal solution.

Thanks.

© Stack Overflow or respective owner