Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with
• keys greater than the node's key. Both the left and right subtrees must also be binary search trees.

Recursion solution:

public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode root, long leftVal, long rightVal) {
        if (root==null) {
            return true;
        }

        if (!(root.val>leftVal&&root.val<rightVal)) {
            return false;
        }

        //pass leftVal for left sub tree since root.left.val should less than root.val
        //pass rightVal for right sub tree since root.val should be less than root.right.val
        return isValidBST(root.left, leftVal, root.val) && isValidBST(root.right, root.val, rightVal);
    }

Iterative solution using inorder traversal, because the current element is always larger than the previous element:

public boolean isValidBSTIter(TreeNode root) {
        if (root == null) {
            return true;
        }

        TreeNode lastVisited = null;

        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();

                // stop the algorithm if the visited nodes are not ordered
                if (lastVisited != null && root.val <= lastVisited.val) {
                    return false;
                }
                lastVisited = root;

                root = root.right;
            }
        }

        return true;
    }