JAVAJEE.COM
Engineering Full Stack Apps with Java and JavaScript
Check if a Binary Tree is a Binary Search Tree (BST) using Inorder Traversal
Normal Login
Approach
-
You can traverse the tree in in-order way, and see if the elements are assending.
-
You may either put the elements into an array and see if the array is sorted in assending way,
-
or while traversing see if the current element is always greater than or equal to previous element.
-
return false is current data is less than previously printed data.
-
may use a static variable to hold the last printed value.
-
-
Solution
Class BSTChecker {
static int LAST = Integer.MIN_VALUE;
boolean isBSTCheck(TreeNode n)
{
if (n == null) return true;
if( ! isBSTCheck(n.left) ) return false;
if( n.data < LAST ) return false;
LAST = n.data;
if( ! isBSTCheck(n.right) ) return false;
return true;
}
}
Complexity
Time complexity is O(N)
Space complexity is O(log N)
- heartin's blog
- Log in or register to post comments