Start learning free

LESSON 412 OF 540 · BINARY TREES

Validate Binary Search Tree in Scala: 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 5
    Ctrl + Enter to check

    SCALA · BINARY TREES

    Validate Binary Search Tree in Scala, explained

    Problem overview

    The method isValidBST gets the root of a binary tree and returns true when it is a valid binary search tree. For every node, every value in its left subtree must be strictly smaller than the node's value, and every value in its right subtree strictly larger. The rule covers the whole subtree, not just the two children. The lesson provides the TreeNode class, with an Int field value and the fields left and right, which are null for a missing child.

    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, but it is the subtle one: each node is in order with its own children (4 < 5 < 6 and 3 < 6 < 7), yet 3 sits in the right subtree of 5, where everything must be larger than 5.

    Approach: every node lives inside a range

    Comparing each node with only its children misses the third example: a child can be fine against its parent and still break a rule set by a node higher up. The check that works describes what is allowed for each node as a range (low, high), with both ends excluded, that every ancestor contributes to:

    • The root can hold any value, so its range is unlimited.
    • When the search goes into the left child of a node, everything there must be smaller than that node. The upper bound becomes the node's value, and the lower bound stays as it was.
    • When it goes into the right child, the lower bound becomes the node's value, and the upper bound stays.

    In [5, 4, 6, null, null, 3, 7], the node 6 gets the range (5, no limit). Its left child, 3, gets the range (5, 6), and 3 is not larger than 5, so the tree is invalid. The rule "the value must be strictly inside the range" is one comparison per node, and each node is visited once, so the time is O(n).

    "No limit yet" needs a value that no node can reach. Node values go from -2^31 to 2^31 - 1, the full range of an Int. If the bounds were Int.MinValue and Int.MaxValue, a root holding either of those values would fail the strict comparison and be rejected, although a single-node tree is valid. The bounds are therefore Long values, which are wider than any Int.

    Step by step

    isValidBST

    1. Call the helper validate on root with Long.MinValue and Long.MaxValue as the bounds, and return its answer. The root has no ancestors, so nothing limits it yet.

    validate

    1. Declare it above isValidBST with a TreeNode named node, two Long bounds low and high, and a Boolean result. It answers whether every value in the tree under node lies strictly between low and high, and the tree itself is valid.
    2. Empty tree: if node == null, return true. An empty tree breaks no rule, and this check also ends the recursion past a leaf.
    3. Out of range: if node.value <= low or node.value >= high, return false. Both comparisons include equality, because duplicates aren't allowed. An Int compared with a Long is widened automatically.
    4. Check both subtrees: the left one with the bounds low and node.value, the right one with node.value and high, joined with &&.

    The solution in Scala

    class Solution {
    def validate(node: TreeNode, low: Long, high: Long): Boolean = {
        if (node == null) {
            return true
        }
        if (node.value <= low || node.value >= high) {
            return false
        }
        return validate(node.left, low, node.value) && validate(node.right, node.value, high)
    }
    def isValidBST(root: TreeNode): Boolean = {
        return validate(root, Long.MinValue, Long.MaxValue)
    }
}

    The Scala details worth noticing:

    • Widening from Int to Long is automatic. node.value <= low compares an Int with a Long without a cast, and validate(node.left, low, node.value) passes an Int where a Long is expected. The widening is always exact.
    • The bounds are exclusive. A node equal to a bound is rejected, so a tree like [2, 2, 2] returns false.
    • && short-circuits. If the left subtree is invalid, the right one isn't searched.
    • Root values at the edge of Int. [2147483647] and [-2147483648] both return true, because Long.MaxValue and Long.MinValue lie beyond any node.
    • null as an empty tree. The check node == null is the base case of the recursion. Without it, the code would read node.value on a missing child.

    Complexity

    Time: O(n). Each node is visited once, and the work per node is two comparisons and two calls. A tree with an invalid node can stop earlier, but the worst case, a valid tree, visits everything.

    Space: O(h) for the recursion, where h is the height of the tree. It is at most 800 here, and about log n for a balanced tree.

    Edge cases and common mistakes

    • Checking only children. [5, 4, 6, null, null, 3, 7] passes a child-only check and returns true, although the right answer is false. The bounds from higher nodes are what catch the 3.
    • Duplicates. [2, 2, 2] returns false, and so does [2147483647, 2147483647], a root with an equal left child. Both comparisons must reject equality.
    • Extreme values with Int bounds. A version using Int.MinValue and Int.MaxValue as the starting bounds returns false for the valid one-node trees [2147483647] and [-2147483648]. Using Long bounds avoids it.
    • Using the wrong bound on the way down. The left child tightens the upper bound, and the right child tightens the lower bound. Swapping them rejects valid trees.
    • Single node. A tree with one node is always valid, whatever its value.
    • Lopsided trees. A tree like [-2147483648, null, 2147483647], with the smallest and the largest value, returns true.

    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.
    • [2147483647] gives true.
    • [-2147483648] gives true.
    • [-2147483648, null, 2147483647] gives true.
    • [2147483647, 2147483647] gives false.
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free