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.

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>();

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;
}