Start learning free

LESSON 415 OF 543 · BINARY TREES

Validate Binary Search Tree in Rust: Passing Bounds Down, 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 None 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,None,None,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,None,None,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 8
    Ctrl + Enter to check

    RUST · BINARY TREES

    Validate Binary Search Tree in Rust, explained

    Problem overview

    The function is_valid_bst receives the root of a binary tree, an Option<Box<TreeNode>>, and returns true if it is a valid binary search tree. The lesson provides TreeNode, with an i32 field val and the fields left and right, both Option<Box<TreeNode>>.

    The rule is about whole subtrees: 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. Equal values are not allowed. Node values can be any 32-bit integer.

    The tree 2 with children 1 and 3 is valid. The tree 5 with children 1 and 4, where 4 has children 3 and 6, is not, because 4 is in the right subtree of 5 and is smaller than 5.

    Approach: every node lives in a range

    The tempting check compares each node only with its children. It is wrong. Take the tree 5 with children 4 and 6, where 6 has children 3 and 7. Every 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 every value must be larger than 5, so the tree is invalid. The rule reaches past the parent.

    The fix is to pass down the range of values a node may hold. The root may hold anything. When the search goes into the left child of a node with value v, everything there must be below v, so the upper bound becomes v and the lower bound stays what it was. For the right child, the lower bound becomes v and the upper bound stays. Each node then only has to be strictly between its two bounds, and all the ancestors' rules are carried by those two numbers.

    On the invalid tree above, the helper sees:

    node 5 must be in (-9223372036854775808, 9223372036854775807)
node 4 must be in (-9223372036854775808, 5)
node 6 must be in (5, 9223372036854775807)
node 3 must be in (5, 6)
  outside

    The node 3 must be larger than 5, which it isn't, so the function returns false there and stops.

    Another way to validate is to read the values in order (left subtree, node, right subtree) and check that they increase strictly. The bounds approach needs no list, and both take O(n) time.

    Step by step

    1. Start the range wide. is_valid_bst ends with a call to Self::validate on &root, with i64::MIN and i64::MAX as the bounds. The root has no ancestors, so nothing limits it yet. The borrow &root lends the tree without moving it.
    2. Write the helper's signature. validate takes node: &Option<Box<TreeNode>> and two i64 bounds, low and high, and returns a bool: whether every value in the tree under node is larger than low and smaller than high.
    3. Make the body a match on node. It has no semicolon after it, so its value is the helper's result.
    4. Empty tree. None => true. An empty tree breaks no rule, and this arm also ends the recursion past a leaf.
    5. Node arm. Some(node) binds the boxed node. Because node is borrowed, node.val and node.left are read, not moved.
    6. Widen the value. let val = node.val as i64, so it can be compared with the i64 bounds.
    7. Reject values outside the range. If val <= low || val >= high, return false. The comparison is strict on both sides, so a value equal to a bound is invalid.
    8. Check the subtrees. The left one gets low and val, and the right one gets val and high. The two calls are joined with &&, with no semicolon.

    The solution in Rust

    impl Solution {
    fn validate(node: &Option<Box<TreeNode>>, low: i64, high: i64) -> bool {
        match node {
            None => true,
            Some(node) => {
                let val = node.val as i64;
                if val <= low || val >= high {
                    return false;
                }
                Self::validate(&node.left, low, val) && Self::validate(&node.right, val, high)
            }
        }
    }

    fn is_valid_bst(root: Option<Box<TreeNode>>) -> bool {
        Self::validate(&root, i64::MIN, i64::MAX)
    }
}

    Rust details worth knowing:

    • Why i64 bounds. Node values can be i32::MIN or i32::MAX. If the starting bounds were i32::MIN and i32::MAX, the strict test would reject a root holding either one. With i64, even i32::MAX is well below i64::MAX, so a single node holding any 32-bit value is accepted.
    • Casting with as i64. Widening an i32 never loses information, so the cast is safe. The helper's own calls pass val, already an i64.
    • Matching on a reference. match node where node is a &Option<Box<TreeNode>> lets the pattern Some(node) bind a reference to the box, thanks to match ergonomics. That is why &node.left is passed on, to keep borrowing the subtree.
    • Early return in an arm. The return false exits this call of validate. The last expression of the arm is the value when the check passes.
    • && short-circuits. If the left subtree is invalid, the right one is not examined.
    • The tree is only borrowed. Neither function consumes anything inside the tree, so the same tree can be checked again.

    Complexity

    Time: O(n), where n is the number of nodes. Each node is visited at most once, with a constant amount of work.

    Space: O(h), where h is the height of the tree, for the recursion. The lesson limits the depth to 800.

    Edge cases and common mistakes

    • Duplicates. The tree 2 with two children both 2 is invalid, and so is 1 with a left child 1. A value equal to a bound is rejected, because the rule says strictly smaller and strictly larger.
    • A deep violation. The tree 2 with children 1 and 3, where 3 has a right child 2, is invalid. The 2 is in the right subtree of 2, so it would have to be larger than 2.
    • Extreme values. A single node holding i32::MIN or i32::MAX is valid. So is a root i32::MAX with a left child i32::MIN, and a root i32::MIN with a right child i32::MAX. Bounds of i32::MIN and i32::MAX would wrongly reject these, which is the reason for the wider type.
    • Comparing only with children. It accepts the tree 5, 4, 6, 3, 7 from the overview, which is invalid.
    • Passing the wrong bound. The left child gets val as its upper bound, the right child as its lower bound. Swapping them rejects valid trees.

    Testing

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