BST - cywongg/2025 GitHub Wiki

public static boolean isBST(BST T) {
return isBSTHelper(T, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public static boolean isBSTHelper(BST T, int min, int max) {
if (T == null) {
return true;
} else if (T.key <= min || T.key >= max) {
return false;
} else {
return isBSTHelper(T.left, min, T.key)
&& isBSTHelper(T.right, T.key, max);
}
}
Explanation:
A BST is a naturally recursive structure, so it makes sense to use a recursive helper to go through the BST
and ensure it is valid. Specifically, our recursive helper will traverse the BST while tracking the minimum
and maximum valid values for subsequent nodes along our current path. We can get these minimum and
maximum values by remembering the key property of BSTs: nodes to the left of our current node are always
less than the current value, and nodes to the right of our current node are always greater than our current
value. So for example, if we encounter a node with value 5, anything to the left must be < 5.
In our base case, an empty BST is always valid. Otherwise, we can check the current node. If it doesn’t fall
within our precomputed min/max, we know this is invalid, and return immediately.
Otherwise, we use the properties of BSTs to bound our subsequent min and max values. If we traverse
to the left, everything must be less than or equal to the current value, so the value of our current node
becomes the new texttt{max} for the tree at T.left. Similar logic applies to the right.