Start learning free

LESSON 408 OF 536 · BINARY TREES

Validate Binary Search Tree in JavaScript: 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

    JAVASCRIPT · BINARY TREES

    Validate Binary Search Tree in JavaScript, explained

    Problem overview

    The method isValidBST(root) receives the root of a binary tree and returns true when it is a valid binary search tree. For every node, all values in its left subtree must be strictly smaller than the node's value, and all values in its right subtree strictly larger. The rule covers the whole subtree, not only the two children. The lesson provides the TreeNode constructor, with val, left and right.

    The tree [2, 1, 3] is valid. The tree [5, 1, 4, null, null, 3, 6] isn't: the right child of 5 is 4, which is smaller than 5. The tree [5, 4, 6, null, null, 3, 7] is the subtle one. 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, so the answer is false.

    Approach: give every node a range

    Comparing each node only with its children misses the third example. A node's value must also fit the limits set by all of its ancestors. The fix is to carry those limits down the recursion as a range (low, high), with both ends exclusive.

    • The root has no limits yet, so it starts with no lower and no upper bound.
    • Going into the left child, the upper bound becomes the current node's value: everything on the left must be smaller. The lower bound stays as it was.
    • Going into the right child, the lower bound becomes the current node's value, and the upper bound stays.

    Every node is checked once against the range it inherits, so the time is O(n). An alternative is to walk the tree in order and check that the values only increase, which also works in O(n). This lesson uses ranges.

    The task's note warns that values can be as small as -2147483648 and as large as 2147483647. A bound that means "no limit yet" therefore can't be one of those numbers, or a valid tree holding that value would be rejected. The solution uses null for "no bound".

    Step by step

    1. In isValidBST, call the helper this.validate(root, null, null) and return its answer. The root has no limits.
    2. Declare validate(node, low, high) above isValidBST. It returns true when every value in the tree under node is larger than low and smaller than high, and a null bound limits nothing.
    3. Return true for an empty tree. !node is true for null. This also ends the recursion past a leaf.
    4. Check the lower bound. If low !== null and node.val <= low, return false. A value equal to the bound breaks the rule too, since the inequality is strict.
    5. Check the upper bound. If high !== null and node.val >= high, return false.
    6. Recurse. The left subtree gets (low, node.val) and the right subtree gets (node.val, high). Join the two calls with &&, so both must be valid.

    The solution in JavaScript

    class Solution {
    validate(node, low, high) {
        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) {
        return this.validate(root, null, null);
    }
}

    The JavaScript details worth knowing:

    • null for "no bound". The guard low !== null && node.val <= low uses && to skip the comparison when there is no bound. !== is true when the two sides differ and converts neither one.
    • Why not 0 or -Infinity. Using 0 would reject negative values. -Infinity would also work, but null with an explicit check makes the "no limit" case clear.
    • !node. The empty tree is null, which is falsy, so !node is true for it. A node object is always truthy, even when its val is 0, so !node never fires for a real node.
    • Short-circuit &&. If the left subtree is invalid, the right call is skipped, because the answer is already false.
    • Numbers. JavaScript numbers are doubles, so 2147483647 and -2147483648 are exact and compare correctly.

    Complexity

    Time: O(n). Each node is visited at most once, and the work per node is two comparisons and two calls.

    Space: O(h) for the recursion, where h is the tree's height. The constraints limit it to 800 levels.

    Edge cases and common mistakes

    • Equal values. [2, 2, 2] is not valid, because the rule is strict. Using < instead of <= in the checks would accept it. The same applies to [1, null, 1].
    • Extreme values. [2147483647] and [-2147483648, null, 2147483647] are valid. A bound that used one of these numbers for "no limit" would reject them wrongly.
    • Comparing only with children. It accepts [5, 4, 6, null, null, 3, 7]. With bounds, the node 3 is checked against the range (5, 6), and the answer is false.
    • A bigger valid tree. [3, 1, 5, 0, 2, 4, 6] is valid. [10, 5, 15, null, null, 6, 20] is not, because 6 is in the right subtree of 10.
    • Swapping the bounds. The left child tightens the upper bound and the right child tightens the lower one. Mixing them up rejects valid trees.

    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.
    • [3, 1, 5, 0, 2, 4, 6] gives true.
    • [2147483647] gives true.
    Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free