Java method to check if a binary tree is a valid BST 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&lt;Bounds&gt; stack = new ArrayDeque&lt;Bounds&gt;();

    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 &lt; lower_bound || curr_node.val &gt; 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.
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 &amp;&amp; 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 &gt;= 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 &lt; lower_bound || curr_node.val &gt; upper_bound) return false;


to 

if (curr_node.val &lt; lower_bound || curr_node.val &gt; upper_bound) {
    return false;
}


Use the diamond inference:

Deque&lt;Bounds&gt; stack = new ArrayDeque&lt;&gt;();


instead of

Deque&lt;Bounds&gt; stack = new ArrayDeque&lt;Bounds&gt;();