LC98. Validate Binary Search Tree

Problem Description

Source: https://leetcode.com/problems/validate-binary-search-tree/

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

A valid 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.

For example: Given binary tree [5, 1, 12, null, null, 15, 16],

    5
   / \
  1  12
    /  \
   15   16

return false, since 15 is the left child of 12, but is greater than 12.

Solution

High level strategy

To check whether a tree is a valid binary search tree, we must compare the value of the current node with the values of its parent or grandparent node. If the current node is the left child of its parent node, then its value cannot be greater than its parent. If the current node is the right child of its parent node, then its value cannot be lesser than its parent. Therefore, as we traverse down the binary search tree, we must pass the value of the current node as the minimum value or the maximum value against which the values of its children will be compared.

To implement our strategy, we will initialize the minimum value and the maximum value with null. We will keep the initial minimum value and pass the value of the current node as the maxmimum value as we recurse down the left side of the current node. We will keep the initial maximum value and pass the value of the current node as the minimum value as we recurse down the right side of the current node. We will return false if the minimum value is greater or equal to the value of the current node, and return false if the maximum value is lesser or equal to the value of the current node. We will only return true if we have reached the leaf of a tree, by which point the binary search tree invariant has yet to be violated. As we recurse back to the bottom-most level of the call stack, we expect both sides of the tree to return true, and we will only return true if and only if both sides return true. The time complexity of this solution is O(n), where 'n' is equal to the number of nodes. The space complexity of this solution is O(h), where h is equal to the height of the tree, which is equal to the log of 'n' on average, where 'n' is equal to the number of nodes. Therefore, the space complexity of this solution can also be expressed in the form of O(logn).

Code

Java

/**
 * 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 isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
        if (root == null) return true;
        if (root.val >= maxVal || root.val <= minVal) return false;
        return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
    }
}

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 **/

const isValidBST = (root) => {
    return helper(root, null, null);
};

const helper = (node, min, max) => {
    if (node === null) return true;
    if (min !== null && min >= node.val) return false;
    if (max !== null && max <= node.val) return false;
    
    return helper(node.left, min, node.val) && helper(node.right, node.val, max);
};

Python

def isValidBST(self, root: TreeNode) -> bool:        
    def validate(node, min_, max_):
        if not node:
            return True 
        if not (min_ < node.val < max_):
            return False 
        return validate(node.left, min_, node.val) and validate(node.right, node.val, max_)
    return validate(root,float('-inf'), float('inf'))