Java method to check if a binary tree is a valid BST

Question

I wrote a Java method (along with a private class) to check if a binary tree is also a binary search tree (BST). I would like some feedback on the design of my solution. Here is a brief description and the code is provided below it :

Do a depth-first traversal of the tree and test if each node satisfies the binary search tree property. The binary search tree property states that a node is valid if its key is greater than every ancestral node in whose right-subtree it resides and less than every ancestral node in whose left-subtree it resides. Instead of checking the node against all of its ancestors, simply check the largest number it should be greater than (its lower bound) and the smallest number it should be less than (its upper bound).

private class Bounds {
 Node node;
 int min_bound;
 int max_bound;
}
public boolean check_if_valid_binary_search_tree(Node node) {
 if (node == null) return true;
 Deque<Bounds> stack = new ArrayDeque<Bounds>();
 Bounds bounds = new Bounds();
 bounds.node = node;
 bounds.max_bound = Integer.MAX_VALUE;
 bounds.min_bound = Integer.MIN_VALUE;
 stack.push(bounds);
 while (!stack.isEmpty()) {
 bounds = stack.pop();
 Node curr_node = bounds.node;
 int lower_bound = bounds.min_bound;
 int upper_bound = bounds.max_bound;
 if (curr_node.val < lower_bound || curr_node.val > upper_bound) return false;
 if (curr_node.left != null) {
 Bounds left = new Bounds();
 left.node = curr_node.left;
 left.max_bound = curr_node.val;
 left.min_bound = lower_bound;
 stack.push(left);
 }
 if (curr_node.right != null) {
 Bounds right = new Bounds();
 right.node = curr_node.right;
 right.min_bound = curr_node.val;
 right.max_bound = upper_bound;
 stack.push(right);
 }
 }
 return true;
}

Note : The approach I use is modelled after a solution written in python by Parker Phinney (of Interview Cake) to the problem of checking if a binary tree is a valid BST.

• coderodde: I had to withdraw my first attempt. The algorithm I am proposing now should be correct.
• Haider: The current approach seems correct. I will compare it more closely with my algorithm once I get some time.
• greybeard: I would like [feedback] on the design of my solution - I see no design. Two approaches come to (my) mind re. check binary tree for BSearchT: inorder traversal and _ both sub-trees BST and root between left and right sub-tree_. You do not motivate handling the stack explicitly.
• Haider: What do you mean by "I see no design" ? Is the solution I propose a blank slate ? Is it wrong ? I am pretty sure, that the solution is functionally correct. If so, then it does have a design and I wanted some feedback on my code.
• greybeard: I see an implementation (- I can try and deduce a design: I'd rather not). For a design, I'd be willing to take a description (especially in form of a javadoc-tool-comment (or several) at the appropriate element(s)/level(s)), a commented interface, a short description with an external reference - hey, even UML will do nicely.

Answer 1

What comes to the actual algorithm, you could traverse the tree in-order and check that node keys are strictly growing. This takes \$\Theta(n)\$ time.

public class Main {
 private static final class TreeNode {
 int key;
 TreeNode left;
 TreeNode right;
 TreeNode parent;
 TreeNode(int key) {
 this.key = key;
 }
 }
 private static TreeNode minimum(TreeNode node) {
 if (node == null) {
 return null;
 }
 while (node.left != null) {
 node = node.left;
 }
 return node;
 }
 private static TreeNode successor(TreeNode node) {
 if (node == null) {
 return null;
 }
 if (node.right != null) {
 return minimum(node.right);
 }
 TreeNode parent = node.parent;
 while (parent != null && parent.right == node) {
 node = parent;
 parent = parent.parent;
 }
 return parent;
 }
 public static boolean isBinarySearchTree(TreeNode root) {
 if (root == null) {
 return true;
 }
 TreeNode node = minimum(root);
 int previousKey = node.key;
 while (true) {
 node = successor(node);
 if (node == null) {
 return true;
 }
 if (previousKey >= node.key) {
 return false;
 }
 previousKey = node.key;
 }
 }
 public static void main(final String... args) {
 // Build a valid BST.
 TreeNode root = new TreeNode(0);
 TreeNode node1 = new TreeNode(-2);
 TreeNode node2 = new TreeNode(2);
 TreeNode nodeBad = new TreeNode(-2);
 root.left = node1;
 node1.parent = root;
 root.right = node2;
 node2.parent = root;
 node1.right = nodeBad;
 nodeBad.parent = node1;
 System.out.println(isBinarySearchTree(root));
 nodeBad.key = -3;
 System.out.println(isBinarySearchTree(root));
 nodeBad.key = -1;
 // Now should print 'true'.
 System.out.println(isBinarySearchTree(root));
 }
}

Naming

Please fix check_if_valid_binary_search_tree to camel case: checkIfValidBinarySearchTree.

Also, not curr_node, but rather currentNode would more appropriate for Java.

Coding conventions

Fix

if (curr_node.val < lower_bound || curr_node.val > upper_bound) return false;

to

if (curr_node.val < lower_bound || curr_node.val > upper_bound) {
 return false;
}

Use the diamond inference:

Deque<Bounds> stack = new ArrayDeque<>();

instead of

Deque<Bounds> stack = new ArrayDeque<Bounds>();

• greybeard: The conventional naming of boolean instance methods without arguments is isCondition() for whatever condition shall hold true. (Regarding code ordering, I prefer following the "natural" ordering of values to check: (current.val < lowerBound || upperBound < current.val))

Answer 2

I am posting an improved version of the algorithm put forward in the question for anyone that might be looking for a more concise answer.

I added a constructor to the Bounds class which allows me to assign the Bounds instance directly into the stack:

stack.push(new Bounds(someNode, someInt, someInt));

I also used the diamond inference (as suggested to me by @coderodde) and fixed the code convention issue.

I have added the Node class that I am using at @greybeard's suggestion. It only has three fields: left child node, right child node and an integer val.

The runtime is \$O(n)\$. The primary advantage it has over @coderodde's solution is that it does not require the existence of the parent node.

public class Node {
 Node left;
 Node right;
 int val;
}
private class Bounds {
 Node node;
 int lower_bound;
 int upper_bound;
 Bounds(Node node, int lower_bound, int upper_bound) {
 this.node = node;
 this.lower_bound = lower_bound;
 this.upper_bound = upper_bound;
 }
}
public boolean checkIfValidBinarySearchTree(Node node) {
 if (node == null) return true;
 Deque<Bounds> stack = new ArrayDeque<>();
 stack.push(new Bounds(node, Integer.MIN_VALUE, Integer.MAX_VALUE));
 while (!stack.isEmpty()) {
 Bounds current = stack.pop();
 Node curr_node = current.node;
 int lower_bound = current.lower_bound;
 int upper_bound = current.upper_bound;
 if (curr_node.val <= lower_bound || curr_node.val >= upper_bound) {
 return false;
 }
 if (curr_node.left != null) {
 stack.push(new Bounds(curr_node.left, lower_bound, curr_node.val));
 }
 if (curr_node.right != null) {
 stack.push(new Bounds(curr_node.right, curr_node.val, upper_bound));
 }
 }
 return true;
}

• greybeard: The self-answer is one of the options suggested in this answer about revised code
• greybeard: You did not pick up suggestions about naming. You tagged your question algorithm, coderodde suggested a different approach you commented to look into given time: did you? The constructor used in Bounds current = new Bounds(); doesn't exist - current isn't used outside the loop, anyway. You include blank lines freely, but no declaration of Node.
• Haider: I didn't add the Nodeclass here as I thought it was too trivial and it's existence should be assumed. But I added it now for completeness. I removed the Bounds current = new Bounds(); declarartion. Thanks for pointing that out.