98. Validate Binary Search Tree

Description

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.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: [2,1,3]

Output: true

Example 2

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.

Solutions

TreeNode

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Solution 1

/**
 * Time complexity : O(N) since we visit each node exactly once.
 * Space complexity : O(N) since we keep up to the entire tree.
 */

class Solution {
    LinkedList<TreeNode> stack = new LinkedList();
    LinkedList<Integer> uppers = new LinkedList();
    LinkedList<Integer> lowers = new LinkedList();

    public void update(TreeNode root, Integer lower, Integer upper) {
        stack.add(root);
        lowers.add(lower);
        uppers.add(upper);
    }

    public boolean isValidBST(TreeNode root) {
        Integer lower = null, upper = null, val;
        update(root, lower, upper);

        while (!stack.isEmpty()) {
            root = stack.poll();
            lower = lowers.poll();
            upper = uppers.poll();

            if (root == null) continue;
            val = root.val;
            
            if (lower != null && val <= lower) return false;
            if (upper != null && val >= upper) return false;
            
            update(root.right, val, upper);
            update(root.left, lower, val);
        }
        return true;
    }
}

Solution 2

/**
 * Time complexity : O(N) since we visit each node exactly once.
 * Space complexity : O(N) since we keep up to the entire tree.
 */

public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }
    
    private boolean helper(TreeNode node, Integer lower, Integer upper) {
        if(node == null) return true;
        
        int val = node.val;
        
        if(lower != null && val <= lower) return false;
        
        if(upper != null && val >= upper) return false;
        
        return helper(node.left, lower, val) && 
                    helper(node.right, val, upper);
    }
}

Solution 3

/**
 * Time complexity : O(N) in the worst case when the tree is a BST or 
 *    the "bad" element is a rightmost leaf.
 * Space complexity : O(N) for the space on the run-time stack.
 */

class Solution {
    // We use Integer instead of int as it supports a null value.
    private Integer prev;

    public boolean isValidBST(TreeNode root) {
        prev = null;
        return inorder(root);
    }

    private boolean inorder(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!inorder(root.left)) {
            return false;
        }
        if (prev != null && root.val <= prev) {
            return false;
        }
        prev = root.val;
        return inorder(root.right);
    }
}

Solution 4

/**
 * Time complexity : O(N) in the worst case when the tree is BST or 
 *    the "bad" element is a rightmost leaf.
 * Space complexity : O(N) to keep stack.
 */
 
 class Solution {
    private Integer prev;
    
    public boolean isValidBST(TreeNode root) {
        if(root == null) {
            return true;
        }
        prev = null;
        return inorder(root);
    }
    
    private boolean inorder(TreeNode node) {
        Stack<TreeNode> stack = new Stack();
        TreeNode curr = node;
        
        while(!stack.isEmpty() || curr != null) {
            while(curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            
            if(prev != null && curr.val <= prev) {
                return false;
            }
            prev = curr.val;
            
            curr = curr.right;
        }
        return true;
    }
}

Follow up