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.

Example 1:

    2
   / \
  1   3

Input: [2,1,3]
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
[code lang="java"]
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        
    }
}
[code]

Idea – 1

val of every node must be within a range. For any bst , root's val must be in (-\infty,\ \infty). Root's left child’s value must be in (-\infty,\ root.val). Root's right child's val must be in (root.val,\ \infty). We apply this check recursively for each node. For an n-node bst, the time complexity is O(n) and average recursion-stack depth is O(\lg{n}). 
[code lang="java"]
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }
    
    private boolean isValidBST(TreeNode x, Integer min, Integer max)
    {
        if(x == null)
        {
            return true;
        }
        
        boolean biggerThanMin = (min == null) || (min < x.val);
        boolean smallerThanMax = (max == null) || (x.val < max);
        
        return biggerThanMin
            && smallerThanMax 
            && isValidBST(x.left, min, x.val) 
            && isValidBST(x.right, x.val, max);
    }
}
[code]

Runtime: 0 ms, faster than 100.00% of Java online submissions for Validate Binary Search Tree.Memory Usage: 37.8 MB, less than 94.08% of Java online submissions for Validate Binary Search Tree.

Idea – 2

Instead of putting pressure on thread's stack space (through recursion), we could use an explicit (heap-allocated) stack and do it iteratively. Asymptotic complexities remain unchanged. 
[code lang="java"]
class Solution {
    
    class StackItem
    {
        TreeNode x;
        Integer min;
        Integer max;
        
        public StackItem(TreeNode x, Integer min, Integer max)
        {
            this.x = x;
            this.min = min;
            this.max = max;
        }
        
        public boolean biggerThanMin()
        { 
            return (this.min == null) || (x.val > this.min); 
        }
        
        public boolean smallerThanMax()
        {
            return (this.max == null) || (x.val < this.max);
        }
    }
    
    public boolean isValidBST(TreeNode root) {
        if(root == null)
        {
            return true;
        }
        
        Deque<StackItem> stack = new ArrayDeque<>();
        stack.addLast( new StackItem(root, null, null) );
        while(!stack.isEmpty())
        {
            StackItem top = stack.removeLast();
            if(!top.biggerThanMin() || !top.smallerThanMax())
            {
                return false;
            }
            
            if(top.x.left != null)
            {
                stack.addLast( new StackItem(top.x.left, top.min, top.x.val) );
            }
            
            if(top.x.right != null)
            {
                stack.addLast( new StackItem(top.x.right, top.x.val, top.max) );
            }
        }
        
        return true;
    }
}
[code]

Runtime: 2 ms, faster than 23.79% of Java online submissions for Validate Binary Search Tree.Memory Usage: 38.6 MB, less than 76.26% of Java online submissions for Validate Binary Search Tree.

Leave a comment