We need to write a function that takes a binary tree and returns true if it is a binary search tree, and false if not.
Review the definition of BST:
For a node, , every data value stored in the subtree rooted at is less than and every data value stored in the subtree rooted at is greater than . An example of a BinarySearchTree is shown in Figure 6.5.
The Wrong Way:
A common way of thinking this problem is: in each node check if (u.left < u < u.right).
u / \ left right
However, this does not cover all the BST cases. such as this one:
head => 4 / \ 1 5 /\ / \ 0 2 3 6
In the above case, every node u satisfies (u.left < u < u.right). However, according to the definition, it is not a BST as node “3” is on the right-hand side of node “4”.
The Correct Way:
Every value of node u, must be within the upper and lower value limit, if they exist. From above example, Node 4 is the head and has no upper or lower bound, so at this stage, it is still a valid node. Node 2 is between node 1(lower bound) and node 4(upper bound), so it is also a valid node. However, Node 3 is not between Node 4 and Node 5.
The question is how do we keep track of the lower and upper bound? 2 Rules:
- At Node u, and traverse to u’s right child, take u’s value as the lower bound.
- At Node u, and traverse to u’s left child, take u’s value as the upper bound.
So the recursive method is like this:
class TreeNode { int value; Node left; Node right; } public static boolean isBST(TreeNode node) { return isBSTHelper(node, null, null); } public static boolean isBSTHelper(TreeNode node, Integer lower, Integer upper){ if (lower!=null && node.value<lower) return false; if (upper!=null && node.value>upper) return false; boolean isLeftBST = true; boolean isRightBST = true; if (node.left!=null){ isLeftBST = isBSTHelper(node.left, lower, node.value); } if (node.right!=null){ isRightBST = isBSTHelper(node.right, node.value, upper); } return isLeftBST && isRightBST; }