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.confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Solution 1

Use stack to traverse through whole tree
Push all left children to stacks, compare left with root, then compare root with right children. BST should follow left < root && root < right. Then pop nodes from stacks so that we could reverse back to upper level. Repeat the comparison until all nodes are compared.

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    public boolean isValidBST(TreeNode root) {
        TreeNode pre = null;
        TreeNode cur = root;
        if (root == null) return true;
        Stack<TreeNode> nodes = new Stack<TreeNode>();
        //deal with left first, compare with mid, store mid and deal right
        while(true) {
            //push all left nodes first, then push and deal right later
            while(cur != null) {
                nodes.push(cur);
                cur = cur.left;
            }
            //pop out 
            if(nodes.isEmpty()) break;
            //if lower level is finished, go up
            if(cur == null) {
                cur = nodes.pop();
            }
            //compare left with mid first, later mid with right, same logic
            if(pre != null && pre.val >= cur.val) {
                return false;
            }
            //finished left brach, compare root with right, go through right branch
            pre = cur;
            cur = cur.right;
        }
        return true;
    }
}

Solution 2

Setting upper bound and lower bound to each node, pass restriction down to the whole tree. Test every node to see if they satisfy requirements

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    public boolean isValidBST(TreeNode root) {
        return validHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean validHelper(TreeNode root, long min, long max) {
        //null node, return true
        if(root == null) return true;
        //check root.val in the range of min and max
        if(root.val <= min || root.val >= max) {
            return false;
        }
        //pass down the restriction
        return validHelper(root.left, min, root.val) 
            && validHelper(root.right, root.val, max);
    }
}

Solution 3

Use recursion to return min max value from left and right node, then compare with root value, need to define a new class representing isBST/min/max, similar to solution 2

Solution 4

Use recursion to do inorder traversal, create a global variable to store temp value

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    TreeNode pre = null;
    public boolean isValidBST(TreeNode root) {
        return dfs(root);
    }
    private boolean dfs(TreeNode root) {
        if(root == null) {
            return true;
        }
        //check left node first
        if(!dfs(root.left)) {
            return false;
        }
        //check root.left with root, then next round root with root.right
        if(pre != null && pre.val >= root.val) {
            return false;
        }
        //store root to pre, so we can compare root with root.right
        pre = root;
        if(!dfs(root.right)) {
            return false;
        }
        return true;
    }
}

Mainly from Yu's Garden