Monday 19 August 2013

Check if a binary tree is a binary search tree

Implement a function to check if a binary tree is a binary search tree.

For binary search tree click here

Solution:

boolean isBST(TreeNode root){
      if(root == null)
            return true;

     return isBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

boolean isBSTHelper(TreeNode root, int min, int max){
     if(root == null)
            return true;

     if(root.data > max || root.data <= min)
            return false;

     if( !isBSTHelper(root.left, min, root.data) || !isBSTHelper(root.right, root.data, max))
            return false;

     return true;
}

Time Complexity : O(N)
Space Complexity : O(logN)

No comments:

Post a Comment