Start learning free

LESSON 412 OF 540 · BINARY TREES

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

    KOTLIN · BINARY TREES

    Validate Binary Search Tree in Kotlin, explained

    Problem overview

    The function isValidBST receives 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 must be strictly larger. The rule covers whole subtrees, not just the two children. The lesson provides the TreeNode class, with an Int field value and nullable left and right children.

    The tree with root 2 and children 1 and 3 is valid. The tree with root 5, left child 1 and right child 4, where 4 has children 3 and 6, is not: the 4 sits in the right subtree of 5 and is smaller. The third example is subtler: root 5 has children 4 and 6, and 6 has children 3 and 7. Every node is in order with its own children, but the 3 lies in the right subtree of 5, so the tree is invalid.

    Approach: every node lives in a range

    Comparing each node only with its children is not enough. Running exactly that check on the third example reports that the tree is fine, which is wrong. A node must fit between all of its ancestors: when you go left from a node, everything below must be smaller than it, and when you go right, everything below must be larger.

    So pass a range down the recursion. The root may hold any value. Going to the left child keeps the lower bound and makes the parent's value the new upper bound. Going to the right child keeps the upper bound and makes the parent's value the new lower bound. A node is valid when its value lies strictly inside its range and both of its subtrees are valid with their narrower ranges.

    The bounds are the tricky part. Node values range over every 32-bit integer, so no Int can stand for "no limit". A root holding Int.MIN_VALUE would fail a strict test against a lower bound of Int.MIN_VALUE. With Int bounds, a single node holding Int.MIN_VALUE and one holding Int.MAX_VALUE are both reported as invalid. Using Long for the bounds fixes this, since every Int is strictly between Long.MIN_VALUE and Long.MAX_VALUE.

    Each node is visited once, so the time is O(n).

    Step by step

    1. Start the check in isValidBST by calling validate(root, Long.MIN_VALUE, Long.MAX_VALUE) and returning the answer. The root has no ancestors, so nothing limits it.
    2. Write the helper's signature: validate(node: TreeNode?, low: Long, high: Long): Boolean. It tells whether every value in the tree under node is greater than low and smaller than high.
    3. Handle an empty tree. If node == null, return true: nothing can break a rule. This also ends the recursion past a leaf.
    4. Check the node's own value. If node.value <= low || node.value >= high, return false. The comparisons are strict, so a value equal to a bound is invalid too.
    5. Check both subtrees and join them with &&. The left subtree gets low and node.value.toLong(), and the right subtree gets node.value.toLong() and high.

    The solution in Kotlin

    class Solution {
    fun 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.toLong()) && validate(node.right, node.value.toLong(), high)
    }

    fun isValidBST(root: TreeNode?): Boolean {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE)
    }
}

    The Kotlin details worth a closer look:

    • No automatic widening. Kotlin never converts an Int to a Long on its own when passing an argument. That is why the calls use node.value.toLong(). Passing the bare Int where a Long parameter is expected does not compile.
    • Comparisons across the two types are allowed. node.value <= low compares an Int with a Long directly, because the number types have comparison operators for each other.
    • Smart cast. After the node == null check returns, Kotlin treats node as non-null, so node.value and node.left need no !!.
    • Short-circuit &&. When the left subtree is invalid, the right one is never visited.
    • Int overflow. Int.MAX_VALUE + 1 wraps around to -2147483648 without any error. The solution never adds to a value, only compares, so it can't overflow.

    Complexity

    Time: O(n). Each node is visited at most once, and each visit does two comparisons and two calls.

    Space: O(h), where h is the height of the tree, for the recursion stack. The tree is at most 800 levels deep.

    Edge cases and common mistakes

    • Checking only children. The third example passes a children-only check and still is not a BST, because the 3 under the 6 is smaller than the 5 at the root.
    • Equal values. The tree [2, 2, 2] is invalid, since the rule is strict on both sides. Using < and > in the failing test, instead of <= and >=, would accept it.
    • Extreme values. A single node holding Int.MAX_VALUE, or Int.MIN_VALUE as the root with Int.MAX_VALUE as its right child, is valid. Bounds of type Int reject these, Long bounds accept them.
    • A single node. [1] is valid.
    • Left child equal to the minimum. [-2147483648, -2147483648] is invalid: the left child is not strictly smaller.
    • Passing the wrong bound. Giving the left subtree the parent's value as its lower bound, or the right subtree as its upper, flips the logic.

    Testing

    Trees are written in level order, with null for a missing child.

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