Validate Binary Search Tree

NeetCode: Validate Binary Search Tree · LeetCode: 98. Validate Binary Search Tree · Difficulty: Medium

A valid BST requires, for every node, that all values in its left subtree are smaller and all values in its right subtree are larger (no duplicates).

Example

Text

Input:  [2, 1, 3]                  Output: true
Input:  [5, 1, 4, null, null, 3, 6]    Output: false   (3 is in the right subtree of 5)

Checking only that each node beats its own children is not enough; the second example passes that check but is invalid.

Trees are given in LeetCode's level-order array form: the root first, then each level from left to right, with null marking a missing node, so [1, 2, 3, 4, 5] is the tree above. The tree(Integer... values) helper in each program builds a TreeNode from such an array by filling children from a queue. TreeNode has the fields val, left, and right. A missing child is null: Java object references are nullable and the fields are mutable, so no wrapper type is needed.

Brute force: compare every node with its entire subtrees

For each node, verify that everything to the left is smaller and everything to the right is larger, then recurse. The all helper takes an IntPredicate, a function from int to boolean, written as a lambda such as v -> v < limit.

Java

import java.util.ArrayDeque;
import java.util.function.IntPredicate;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        int limit = root.val;
        return all(root.left, v -> v < limit)
                && all(root.right, v -> v > limit)
                && isValidBST(root.left)
                && isValidBST(root.right);
    }

    private boolean all(TreeNode node, IntPredicate ok) {
        if (node == null) return true;
        return ok.test(node.val) && all(node.left, ok) && all(node.right, ok);
    }
}

public class Main {
    /** Builds a tree from LeetCode's level-order array, where null marks a missing node. */
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.poll();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().isValidBST(tree(2, 1, 3)));
        System.out.println(new Solution().isValidBST(tree(5, 1, 4, null, null, 3, 6)));
    }
}

Output

true
false

Time: O(n²) worst case. Space: O(h).

Optimal: pass down the allowed range

Every node must lie strictly between a lower and an upper bound inherited from its ancestors. The root may be anything. Going left, the current value becomes the new upper bound; going right, it becomes the new lower bound. Node values are int, and a node may hold Integer.MIN_VALUE or Integer.MAX_VALUE. Using long bounds (starting at Long.MIN_VALUE and Long.MAX_VALUE) keeps those values valid, because no int equals either bound.

Java

import java.util.ArrayDeque;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean check(TreeNode node, long low, long high) {
        if (node == null) return true;
        long v = node.val;
        return low < v && v < high && check(node.left, low, v) && check(node.right, v, high);
    }
}

public class Main {
    /** Builds a tree from LeetCode's level-order array, where null marks a missing node. */
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.poll();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().isValidBST(tree(2, 1, 3)));
        System.out.println(new Solution().isValidBST(tree(5, 1, 4, null, null, 3, 6)));
        System.out.println(new Solution().isValidBST(tree(2, 2, 2)));
        System.out.println(new Solution().isValidBST(tree(Integer.MIN_VALUE, null, Integer.MAX_VALUE)));
    }
}

Output

true
false
false
true

Time: O(n). Space: O(h).