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)
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