Java method to check 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;();