Leetcode: 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.

Understand the problem:
The problem asks for validating if a binary tree is a binary search tree. So we must first understand what is a BST? Basically, a BST is a binary tree where nodes are ordered in the following way:

• each node contains one key, also known as data
• the keys in the left subtree are less than the key in its parent node
• the keys in the right subtree are greater than the key in the parent node
• duplicated keys are not allowed.

Consequently, it is not hard to find that BST is defined in a recursive way. So we may use DFS to traverse the tree.

Solution:
Since the BST is defined as left children is less than the parent, while right children is greater than the parent. So we can in inorder traversal to traverse the tree. We use inorder traverse because it goes to left child first, then parent, then right child. They should be ordered in a ascending order, if it is a BST.

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int min = Integer.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;

        return inOrderTraverse(root);
    }
    
    public boolean inOrderTraverse(TreeNode node) {
        if (node == null) return true;
        
        if (inOrderTraverse(node.left) == false) return false;
        
        if (node.val > min) {
            min = node.val;
        } else return false;
        
        
        if (inOrderTraverse(node.right) == false) return false;
        
        return true;
    }
}

Another Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int min = Integer.MIN_VALUE;
    private boolean ret = true;
    
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;

        inOrderTraverse(root);
        return ret;
    }
    
    public void inOrderTraverse(TreeNode node) {
        if (node == null || ret == false) return;
        
        inOrderTraverse(node.left);
        
        if (node.val > min) {
            min = node.val;
        } else {
            ret = false;
            return;
        }
        
        inOrderTraverse(node.right);
    }
}

Discussion:
Both solution 1 and 2 are based on inorder traversal. In the first solution, the recursive function has a return value. Be careful about the recursive function with a return value. In t he second solution, it is more close to inorder traversal. Note that it needs to use a global variable to save the return value. 


Another solution:
Remember that the BST is left children is smaller than the key, while the right ones are greater. We can use this property to recursively validate that.

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    private boolean isBST(TreeNode node, int min, int max) {
        if (node == null) return true;
        
        if (node.val <= min || node.val >= max) {
            return false;
        }
        
        return isBST(node.left, min, node.val) && isBST(node.right, node.val, max);
    }
}

Summary:
In this post, we learned how to validate a binary tree is a BST. For the tree related question, there are two major ways to consider, DFS and BFS. 

Update 10/28/14:

public class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        
        int prev = Integer.MIN_VALUE;
        
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                TreeNode curr = stack.pop();
                if (curr.val <= prev) {
                    return false;
                }
                
                prev = curr.val;
                
                p = curr.right;
            }
        }
        
        return true;
    }
}

Update on 2/16/15:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isBST(root, null, null);
    }
    
    private boolean isBST(TreeNode node, Integer min, Integer max) {
        if (node == null) return true;
        
        if ((min != null && node.val <= min) || (max != null && node.val >= max)) {
            return false;
        }
        
        return isBST(node.left, min, node.val) && isBST(node.right, node.val, max);
    }
}

Update on 4/30/19

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

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) {
        // write your code here
        if (root == null) {
            return true;
        }

        ResultType ans = isValidBSTHelper(root);
        return ans.isBST;
    }

    private ResultType isValidBSTHelper(TreeNode root) {
        if (root == null) {
            return new ResultType(Integer.MIN_VALUE, Integer.MAX_VALUE, true);
        }

        ResultType left = isValidBSTHelper(root.left);
        ResultType right = isValidBSTHelper(root.right);
        
        if (!left.isBST || !right.isBST) {
            return new ResultType(0, 0, false);
        }
        
        if (root.left != null && root.val <= left.max) {
            return new ResultType(0, 0, false);
        }
        
        if (root.right != null && root.val >= right.min) {
            return new ResultType(0, 0, false);
        }

        int max = Math.max(root.val, right.max);
        int min = Math.min(root.val, left.min);

        return new ResultType(max, min, true);
    }
}

class ResultType {
    int max;
    int min;
    boolean isBST;

    public ResultType(int max, int min, boolean isBST) {
        this.max = max;
        this.min = min;
        this.isBST = isBST;
    }
}