Suppose we have the following code with a data structure, TreeNode, and a method, isValidBST.
Definition: A given binary tree T is a valid Binary Search Tree (BST) if and only if:
- The left subtree contains only values strictly less than the value in the root node.
- The right subtree contains only values strictly greater than the value in the root node.
- All subtrees are valid BSTs.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) {this.val = val;}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public boolean isValidBST(TreeNode root) {
// TODO
}
And we are asked to implement the method isValidBST, which, given a TreeNode, namely root, returns a boolean indicating whether root is the root of a valid Binary Search Tree. Okay. Let's go.
The third requirement, that all subtrees must also be valid BSTs, implies that whatever BST-validating procedure we run on the root node, that procedure should also validate our subtrees. Okay: subproblems with a base case.... Can you say recursion?
Indeed a recursive method is an excellent strategy, here.
For our first try, then, let's write a method that confirms whether a node is greater than its left child and less than its right child:
public boolean isValidBST(TreeNode root) {
// TODO
if (root == null) return true; // empty tree is valid by convention.
if (root.left == null && root.right == null) return true; // tree of one node is valid.
if (root.left == null) {
return root.val < root.right.val;
} else if (root.right == null) {
return root.left.val < root.val;
} else {
return root.val < root.right.val && root.left.val < root.val;
}
}
Running this case we find that the binary tres [], [1], and [2,1,3] pass. But observe the BST:
Example 1:
[5,1,7,null,null,3,8]
Example 1 passes our validator but in fact is not a BST. (Why?)
We have confirmed the bounds of the root node and its immediate children. We have even confirmed that the tree's left and right subtrees are themselves valid BSTs. But with respect to the root node, the right subtree is not a valid BST because it contains an element not greater than the root's value. We missed this because our method checked this element's bounds only with respect to its immediate parent, and not with respect to its
In other words we have neglected our recursive step; and indeed, reading over our code again, it doesn't contain any recursive calls.
As we descend the tree, a node's value must satisfying increasingly tight lower and upper bounds. Encoding a flexible requirement is exactly what parameters are for. Define a helper method with a signature that will us to pass tightening bounds through succeeding recursive calls.
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean isValidBST(TreeNode node, int min, int max) {
if (node == null) return true; // empty tree is valid BST by convention.
if (node.left == null && node.right == null) {
return isWithinBounds(node.val, min, max);
} else if (node.left == null) {
return isWithinBounds(node.val, min, max)
&& isValidBST(node.right, node.val, max);
} else if (node.right == null) {
return isWithinBounds(node.val, min, max)
&& isValidBST(node.left, min, node.val);
} else {
return isWithinBounds(node.val, min, max)
&& isValidBST(node.left, min, node.val)
&& isValidBST(node.right, node.val, max);
}
}
private boolean isWithinBounds(int val, int min, int max) {
return min < val && val < max;
}
Great, our validator now properly rejects trees with a left-subtree element not less than the root value, and it rejects trees containing a right-subtree element not greater than the root value. Good.
But now there's another problem: the single-node tree [2147483647] fails when it should pass.
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean isValidBST(TreeNode node, int min, int max) {
if (node == null) return true;
if (node.left == null && node.right == null)
return isWithinBounds(node.val, min, max);
else if (node.left == null) {
return isWithinBounds(node.val, min, max)
&& isValidBST(node.right, node.val, max);
} else if (node.right == null) {
return isWithinBounds(node.val, min, max)
&& isValidBST(node.left, min, node.val);
} else {
return isWithinBounds(node.val, min, max)
&& isValidBST(node.right, node.val, max)
&& isValidBST(node.left, min, node.val);
}
}
private boolean isWithinBounds(int val, Integer min, Integer max) {
boolean lb = false; boolean ub = false;
if (min == Integer.MIN_VALUE) {
lb = min <= val;
} else lb = min < val;
if (max == Integer.MAX_VALUE) {
ub = val <= max;
} else ub = val < max;
returb lb && ub;
}
To understand why our implementation is wrong, recall the definition of recursion.
By setting Integer.MIN_VALUE and Integer.MAX_VALUE we have set arbitrarily extreme boundaries, when the problem actually calls for a programmatic representation of no boundaries yet given, i.e. infinity. As we see, representing infinity with extreme integer values turns out not to work. We must distinguish extreme bounds of Integer.MIN_VALUE (-2^31) or Integer.MAX_VALUE (2^31 - 1) from not having no bound at all (i.e. infinite bounds) in a different way.
Java's primitive integer type int has no empty value. But using Java's integer-wrapper Integer, we can have a null integer, and it works at last.
Observe:
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
private boolean isValidBST(TreeNode node, Integer min, Integer max) {
if (node == null) return true;
if (node.left == null && node.right == null)
return isWithinBounds(node.val, min, max);
else if (node.left == null) {
return isWithinBounds(node.val, min, max)
&& isValidBST(node.right, node.val, max);
} else if (node.right == null) {
return isWithinBounds(node.val, min, max)
&& isValidBST(node.left, min, node.val);
} else {
return isWithinBounds(node.val, min, max)
&& isValidBST(node.right, node.val, max)
&& isValidBST(node.left, min, node.val);
}
}
private boolean isWithinBounds(int val, Integer min, Integer max) {
if (min == null && max == null) return true;
else if (min == null)
return val < max;
else if (max == null)
return min < val;
else {
return min < val && val < max;
}
}