mediumTrees

Validate Binary Search Tree

Check whether a binary tree is a strict binary search tree: every left descendant is smaller and every right descendant is larger. Duplicate values are invalid.

LeetCode ↗

Work through the cases

3 examples

Input notation

A binary tree in level order on one line, using null for missing children. Omit trailing nulls; use null for an empty tree.

Expected result

true or false.

Case 1

Input

2 1 3

Expected output

true

Case 2

Input

5 1 7 null null 4 8

Expected output

false

Case 3

Input

2 2 3

Expected output

false

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Checking only “left < root < right” is not enough: the maximum in the left subtree must also be less than the root. We can pass an allowed range, or use the BST fact that inorder is strictly increasing. During inorder, remember the previous value; the current one must be larger. Recurse left, compare, recurse right — one pass finds a violation. An empty tree is valid.

We can perform a recursive in-order traversal on the binary tree. If the result of the traversal is strictly ascending, then this tree is a binary search tree.

Therefore, we use a variable prev to save the last node we traversed. Initially, prev = -∞. Then we recursively traverse the left subtree. If the left subtree is not a binary search tree, we directly return False. Otherwise, we check whether the value of the current node is greater than prev. If not, we return False. Otherwise, we update prev to the value of the current node, and then recursively traverse the right subtree.

The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.

/**
 * 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;
 *     }
 * }
 */
class Solution {
    private TreeNode prev;

    public boolean isValidBST(TreeNode root) {
        return dfs(root);
    }

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

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.