In the previous article, I covered a level-order traversal of a binary tree in Rust. This time, I want to take on a classic problem from LeetCode #98: Validate Binary Search Tree.

The challenge asks us to determine if a binary tree is a valid Binary Search Tree (BST). For a tree to be a valid BST:

  • The left subtree of a node must contain only values less than the node’s value.
  • The right subtree of a node must contain only values greater than the node’s value.
  • Both left and right subtrees must themselves also be valid BSTs.

Rust Tree Representation

The LeetCode problem defines the tree structure for us. In Rust, shared ownership with mutable access is tricky, which is why the common representation uses Rc<RefCell<T>>.

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}
  • Rc (Reference Counted) allows multiple owners of the same tree node.
  • RefCell provides interior mutability — so we can borrow nodes mutably at runtime.

This combination is more complex than what you’d see in languages like Python or Java, where a recursive solution would be trivial. But Rust’s ownership model forces explicitness and safety.

Iterative Validation with Bounds

The key idea of validating a BST is range propagation. For every node, its value must lie strictly between some min and max bounds.

  • For the root, the bounds are (-∞, +∞).
  • When going left, the new maximum becomes the parent’s value.
  • When going right, the new minimum becomes the parent’s value.

Instead of recursion, we can use a queue (VecDeque) to track nodes along with their current valid range:

use std::collections::VecDeque;

struct Solution;

impl Solution {
    pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        let mut queue = VecDeque::new();
        queue.push_back((root.clone(), i64::MIN, i64::MAX));

        while let Some((Some(r), min, max)) = queue.pop_front() {
            // Runtime borrow check - panics if already mutably borrowed
            // The borrow is automatically released at the end of this scope
            let r = r.borrow();
            let r_val = r.val as i64;

            if !(min < r_val && r_val < max) {
                return false;
            }

            if r.left.is_some() {
                queue.push_back((r.left.clone(), min, r_val));
            }
            if r.right.is_some() {
                queue.push_back((r.right.clone(), r_val, max));
            }
        }

        true
    }
}

Why Use VecDeque Instead of Vec?

In Rust, both Vec and VecDeque can act as stacks for managing nodes during traversal. The difference comes down to semantics and cost:

  • Vec gives O(1) push/pop at the end, which makes it ideal for depth-first traversal (DFS).
  • VecDeque gives O(1) push/pop at both ends, which makes it more natural for breadth-first traversal (BFS).

In this solution, we’re conceptually doing a level-order check with explicit bounds, so VecDeque matches the intent: it lets us push children to the back and pop from the front without awkward indexing tricks.

Could you use Vec here? Absolutely. You’d just push and pop at the end, effectively turning it into a DFS instead of a BFS. The algorithm would still be correct, since the order of processing nodes doesn’t matter for BST validation — each node is checked independently against its range.

But choosing VecDeque is a matter of clarity: it makes the traversal style explicit, and avoids confusing readers about whether the algorithm relies on DFS ordering (it doesn’t).

Why i64 for an i32 Tree?

Notice that we cast values into i64. This avoids overflow when handling edge cases like i32::MIN and i32::MAX. Without this widening, propagating bounds could wrap incorrectly.

Why Avoid Recursion?

Many textbook solutions use recursion, but in Rust, iterative solutions are often safer and faster:

  1. Stack Growth Recursive calls grow the program’s call stack, which is limited. For large trees, deep recursion risks stack overflow. Iteration avoids this entirely.

  2. Performance Each recursive call carries overhead. Rust doesn’t automatically perform tail call optimization, so recursion may result in unnecessary function call frames. Iteration with an explicit queue (VecDeque) avoids that.

  3. Control Over State Iteration lets you manage additional state (like min/max ranges) without threading parameters through recursive calls. This leads to cleaner Rust code.

  4. Interior Mutability Considerations Using RefCell moves borrow checking from compile time to runtime. That introduces a slight dynamic cost, but in practice it’s negligible here. Still, being explicit about iteration means you know exactly when borrows are taken and released.

Complexity Analysis

  • Time Complexity: O(n), since each node is visited once.
  • Space Complexity: O(n), since in the worst case the queue may hold all nodes at a given level.

This is identical to a recursive approach in asymptotic terms, but avoids call stack limitations.

Comparison: Inorder Traversal Approach

An alternative approach is an inorder traversal. In a valid BST, the inorder sequence is strictly increasing. You could store the last visited value and check ordering.

That works, but I prefer the explicit range propagation method: it avoids subtle bugs (like initializing “previous” incorrectly), and it maps more naturally to Rust’s ownership semantics.

Test Cases

The classic examples illustrate both valid and invalid BSTs.

#[cfg(test)]
mod tests {
    use super::*;

    /// ## Example 1: Valid BST
    ///    2
    ///   / \
    ///  1   3
    #[test]
    fn case1() {
        let mut root = TreeNode::new(2);
        root.left = Some(Rc::new(RefCell::new(TreeNode::new(1))));
        root.right = Some(Rc::new(RefCell::new(TreeNode::new(3))));

        assert!(Solution::is_valid_bst(Some(Rc::new(RefCell::new(root)))));
    }

    /// ## Example 2: Invalid BST
    ///        5
    ///       / \
    ///      1   4
    ///         / \
    ///        3   6
    #[test]
    fn case2() {
        let mut root = TreeNode::new(5);
        root.left = Some(Rc::new(RefCell::new(TreeNode::new(1))));

        let mut right = TreeNode::new(4);
        right.left = Some(Rc::new(RefCell::new(TreeNode::new(3))));
        right.right = Some(Rc::new(RefCell::new(TreeNode::new(6))));

        root.right = Some(Rc::new(RefCell::new(right)));

        assert!(!Solution::is_valid_bst(Some(Rc::new(RefCell::new(root)))));
    }

    /// ## Edge Cases
    /// - Single node tree with `i32::MIN`
    /// - Invalid tree where right child equals parent
    #[test]
    fn case_edge_values() {
        // Single node with i32::MIN is valid
        let root = TreeNode::new(i32::MIN);
        assert!(Solution::is_valid_bst(Some(Rc::new(RefCell::new(root)))));

        // Invalid because right child equals parent
        let mut root = TreeNode::new(i32::MAX);
        root.right = Some(Rc::new(RefCell::new(TreeNode::new(i32::MAX))));
        assert!(!Solution::is_valid_bst(Some(Rc::new(RefCell::new(root)))));
    }
}

Conclusion

This problem is a good example of how recursive textbook solutions don’t always map well to Rust. By making the state explicit with a VecDeque, we avoid stack overflows, reduce overhead, and stay in full control of ownership and borrowing rules.

When solving algorithmic problems in Rust, always question whether recursion is the right tool — often, an iterative solution is both safer and more idiomatic.