Start learning free

LESSON 412 OF 540 · BINARY TREES

Validate Binary Search Tree in TypeScript: Passing Bounds Down in O(n)

Practice O(n) Read the full explanation

Given the root of a binary tree, return true if it is a valid binary search tree (BST), and false otherwise.

A binary tree is a valid BST when, for every node:

  • every value in its left subtree is strictly smaller than the node's value,
  • every value in its right subtree is strictly larger than the node's value.

The rule is about the whole subtree, not only the children: a node's value must also fit every node above it.

The trees below are written in level order (top to bottom, left to right), with null for a missing child.

 

Example 1:

     2
    / \
   1   3

Input: root = [2,1,3]
Output: true
Explanation: 1 is smaller than 2 and 3 is larger.

Example 2:

     5
    / \
   1   4
      / \
     3   6

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The right child of the root 5 is 4, which is smaller than 5.

Example 3:

     5
    / \
   4   6
      / \
     3   7

Input: root = [5,4,6,null,null,3,7]
Output: false
Explanation: Every node is in order with its own children: 4 < 5 < 6 and 3 < 6 < 7. But 3 is in the right subtree of 5, where every value must be larger than 5. Comparing each node only with its children misses this: each node must lie in the range that all of its ancestors set.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • Each node value is between -231 and 231 - 1.
  • The tree is at most 800 levels deep.

Note:

Your algorithm should run in O(n) time, where n is the number of nodes, visiting each node once.

Node values can be the smallest and the largest 32-bit integers, so a bound that means "no limit yet" can't be one of those values.

STEP 1 OF 6
    Ctrl + Enter to check

    TYPESCRIPT · BINARY TREES

    Validate Binary Search Tree in TypeScript, explained

    Problem overview

    The method isValidBST(root) receives the root of a binary tree and returns true if it is a valid binary search tree. The tree is valid when, for every node, all values in its left subtree are strictly smaller than the node's value and all values in its right subtree are strictly larger. The rule covers the whole subtree, not just the two children. The lesson provides the TreeNode type: a node has a number val and two children, left and right, each a node or null.

    The tree [2,1,3] is valid. The tree [5,1,4,null,null,3,6] is not, because the right child of 5 is 4, which is smaller. The tree [5,4,6,null,null,3,7] is not valid either, and it shows the real difficulty: every node is in order with its own children (4 < 5 < 6 and 3 < 6 < 7), but 3 sits in the right subtree of 5, where every value must be larger than 5.

    Approach: every node lives in a range

    Comparing each node only with its children misses the third tree. What a node has to respect comes from all of its ancestors: each time the path goes left at a node, that node's value becomes an upper limit for everything below, and each time it goes right, that value becomes a lower limit.

    So the check carries a range (low, high) down the recursion. The root has no limits. For a node with value v in the range (low, high):

    • its value must be strictly above low and strictly below high;
    • its left subtree gets the range (low, v);
    • its right subtree gets the range (v, high).

    In [5,4,6,null,null,3,7], the node 3 is reached by going right at 5 and then left at 6, so its range is (5, 6), and 3 is outside it.

    A bound that means "no limit yet" can't be a number, because node values can be as small and as large as the smallest and largest 32-bit integers. So the "no limit" is null.

    Step by step

    1. Start the check. isValidBST calls this.validate(root, null, null) and returns its answer: nothing limits the root yet.
    2. Declare the helper validate(node: TreeNode | null, low: number | null, high: number | null): boolean. It tells whether every value under node is above low and below high, where a null bound limits nothing.
    3. Empty tree. If !node, return true. An empty tree breaks no rule, and this also ends the recursion past a leaf.
    4. Check the lower bound. If low !== null && node.val <= low, return false. The comparison is strict in the other direction: a value equal to the bound breaks the rule.
    5. Check the upper bound. If high !== null && node.val >= high, return false.
    6. Recurse. The left subtree keeps low and gets node.val as its upper bound. The right subtree gets node.val as its lower bound and keeps high. Both must be valid, so the two calls are joined with &&.

    The solution in TypeScript

    class Solution {
    validate(node: TreeNode | null, low: number | null, high: number | null): boolean {
        if (!node) {
            return true;
        }
        if (low !== null && node.val <= low) {
            return false;
        }
        if (high !== null && node.val >= high) {
            return false;
        }
        return this.validate(node.left, low, node.val) && this.validate(node.right, node.val, high);
    }

    isValidBST(root: TreeNode | null): boolean {
        return this.validate(root, null, null);
    }
}

    Details worth knowing:

    • Why the null checks are needed. In JavaScript, null becomes 0 in a numeric comparison. With const low: number | null = null and const val = -3, the expression val <= low is true, so an unguarded check would reject a valid negative value. low !== null && val <= low is false, as it should be.
    • The union type. number | null says that a bound is either a number or null. It exists only for the compiler and is erased in the JavaScript output. At run time, !== null is what tells the cases apart.
    • !node. A TreeNode object is always truthy, even when its val is 0, so !node is true only for null (or undefined). It checks the node, not the node's value.
    • Short-circuit &&. When the left subtree is already invalid, the right one isn't searched, since the answer is false anyway.
    • Number precision. Values up to 2^31 - 1 are exactly representable in a TypeScript number, so the bounds never lose precision.

    Complexity

    Time: O(n), where n is the number of nodes. Each node is visited once, plus one call for each missing child, with constant work per call.

    Space: O(h) for the recursion, where h is the height of the tree: up to the 800 levels the constraints allow, or O(log n) for a balanced tree.

    Edge cases and common mistakes

    • Comparing only with the children. This accepts [5,4,6,null,null,3,7]. Carrying the range is what rejects it.
    • Duplicates. The inequalities are strict, so [2,2,2] is not valid, and neither is [1,null,1].
    • Extreme values. [2147483647] and [-2147483648] are valid single nodes. The tree [-2147483648,null,2147483647] is valid too. Using the smallest and largest integers as "no limit" would reject some of these, which is why null is used.
    • Zero. [0,-1] is valid. A check like if (low && ...) would treat a bound of 0 as "no bound". Comparing with !== null avoids that.
    • Single node or empty subtrees. A leaf, or a tree of one node, is always valid.
    • Using < where <= is needed. The rejection tests are <= and >= because equal values break the rule.

    Testing

    • [2,1,3] gives true.
    • [5,1,4,null,null,3,6] gives false.
    • [5,4,6,null,null,3,7] gives false.
    • [2,2,2] gives false.
    • [-2147483648,null,2147483647] gives true.
    • [0,-1] gives true.
    • [3,1,5,0,2,4,6] gives true.
    • [5,1,6,null,null,5,7] gives false: the 5 in the right subtree equals the root.
    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free