Validate if Tree is BST in DSA Rust

Mental Model

A binary search tree (BST) is a tree where every node's left child is smaller and right child is bigger than the node itself.

Analogy: Think of a phone book where names are sorted. Every page to the left has names that come before the current name, and every page to the right has names that come after.

    10
   /  \
  5    15
 / \     \
2   7     20

Dry Run Walkthrough

Input: Tree: 10 -> left: 5 -> left: 2, right: 7; right: 15 -> right: 20

Goal: Check if this tree follows BST rules where left < node < right for all nodes

Step 1: Start at root 10, set allowed range (-∞, +∞)

Node=10, Range=(-∞, +∞)

Why: We begin with no limits for root value

Step 2: Check left child 5 with range (-∞, 10)

Node=5, Range=(-∞, 10)

Why: Left child must be less than 10

Step 3: Check left child of 5: 2 with range (-∞, 5)

Node=2, Range=(-∞, 5)

Why: Left child of 5 must be less than 5

Step 4: 2 has no children, return true

Leaf node 2 validated

Why: Leaf nodes are valid if in range

Step 5: Check right child of 5: 7 with range (5, 10)

Node=7, Range=(5, 10)

Why: Right child of 5 must be greater than 5 and less than 10

Step 6: 7 has no children, return true

Leaf node 7 validated

Why: Leaf nodes are valid if in range

Step 7: Check right child 15 with range (10, +∞)

Node=15, Range=(10, +∞)

Why: Right child must be greater than 10

Step 8: Check right child of 15: 20 with range (15, +∞)

Node=20, Range=(15, +∞)

Why: Right child of 15 must be greater than 15

Step 9: 20 has no children, return true

Leaf node 20 validated

Why: Leaf nodes are valid if in range

Result:

Tree is a valid BST

Annotated Code

DSA Rust

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

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

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn is_bst_helper(node: Option<Rc<RefCell<TreeNode>>>, min: Option<i32>, max: Option<i32>) -> bool {
    if let Some(n) = node {
        let val = n.borrow().val;
        // Check if current node violates min/max constraints
        if let Some(min_val) = min {
            if val <= min_val {
                return false;
            }
        }
        if let Some(max_val) = max {
            if val >= max_val {
                return false;
            }
        }
        // Recursively check left subtree with updated max
        if !is_bst_helper(n.borrow().left.clone(), min, Some(val)) {
            return false;
        }
        // Recursively check right subtree with updated min
        if !is_bst_helper(n.borrow().right.clone(), Some(val), max) {
            return false;
        }
        true
    } else {
        true
    }
}

fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    is_bst_helper(root, None, None)
}

fn main() {
    // Build tree:
    //      10
    //     /  \
    //    5    15
    //   / \     \
    //  2   7     20
    let root = TreeNode::new(10);
    let left = TreeNode::new(5);
    let right = TreeNode::new(15);
    let left_left = TreeNode::new(2);
    let left_right = TreeNode::new(7);
    let right_right = TreeNode::new(20);

    root.borrow_mut().left = Some(left.clone());
    root.borrow_mut().right = Some(right.clone());
    left.borrow_mut().left = Some(left_left);
    left.borrow_mut().right = Some(left_right);
    right.borrow_mut().right = Some(right_right);

    let result = is_valid_bst(Some(root));
    println!("Is valid BST? {}", result);
}

if let Some(min_val) = min { if val <= min_val { return false; } }

Check if current node value is not smaller than allowed minimum

if let Some(max_val) = max { if val >= max_val { return false; } }

Check if current node value is not bigger than allowed maximum

if !is_bst_helper(n.borrow().left.clone(), min, Some(val)) { return false; }

Recursively validate left subtree with updated max limit

if !is_bst_helper(n.borrow().right.clone(), Some(val), max) { return false; }

Recursively validate right subtree with updated min limit

Output

Is valid BST? true

Complexity Analysis

Time: O(n) because we visit each node once to check BST property

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to checking in-order traversal array for sortedness (also O(n)), this method uses less extra space and checks constraints directly

Edge Cases

Empty tree

Returns true because empty tree is a valid BST

DSA Rust

if let Some(n) = node { ... } else { true }

Single node tree

Returns true because single node satisfies BST rules

DSA Rust

if let Some(n) = node { ... } else { true }

Tree with duplicate values

Returns false because BST does not allow duplicates on left or right

DSA Rust

if val <= min_val { return false; } and if val >= max_val { return false; }

When to Use This Pattern

When asked if a binary tree is a BST, use range limits to check each node's value fits between allowed min and max values.

Common Mistakes

Mistake: Only checking immediate children values without considering entire subtree range
Fix: Pass down min and max limits to all recursive calls to ensure all descendants fit BST rules

Summary

Checks if a binary tree follows the binary search tree property by validating node values within allowed ranges.

Use when you need to confirm a tree is a BST before performing BST-specific operations.

The key insight is to track and update min and max limits for each subtree to validate all nodes correctly.

Practice

1. What does it mean for a binary tree to be a Binary Search Tree (BST)?

easy

A. Every node's left subtree contains only nodes with values less than the node's value, and the right subtree only nodes with values greater.

B. Every node has exactly two children.

C. All nodes have the same value.

D. The tree is balanced with equal height on both sides.

Solution

1. Step 1: Understand BST property

   A BST requires that for each node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater.

2. Step 2: Compare options with definition

   Every node's left subtree contains only nodes with values less than the node's value, and the right subtree only nodes with values greater. correctly states this property, while others describe different tree properties.

3. Final Answer:

   Every node's left subtree contains only nodes with values less than the node's value, and the right subtree only nodes with values greater. -> Option A

4. Quick Check:

   BST property = Every node's left subtree contains only nodes with values less than the node's value, and the right subtree only nodes with values greater. [OK]

Hint: BST means left < node < right for all nodes [OK]

Common Mistakes:

• Confusing BST with balanced tree
• Thinking all nodes must have two children
• Assuming all values are equal

2. Which Rust function signature correctly represents a function to check if a binary tree is a BST?

easy

A. fn is_bst(root: &TreeNode) -> i32

B. fn is_bst(root: TreeNode) -> bool

C. fn is_bst(root: &Option) -> bool

D. fn is_bst(root: Option<TreeNode>) -> String

Solution

1. Step 1: Understand Rust tree node usage

   Binary trees in Rust are often represented as Option to allow for empty nodes and heap allocation.

2. Step 2: Check function signature return type

   The function should return a boolean indicating if the tree is a BST, so return type bool is correct.

3. Final Answer:

   fn is_bst(root: &Option) -> bool -> Option C

4. Quick Check:

   Correct Rust signature = fn is_bst(root: &Option) -> bool [OK]

Hint: Use &Option and bool return for BST check [OK]

Common Mistakes:

• Using TreeNode directly without Option or Box
• Returning wrong type like i32 or String
• Not using reference for input parameter

3. Given the following Rust code snippet, what will be the output?

struct TreeNode {
    val: i32,
    left: Option,
    right: Option,
}

fn is_bst(node: &Option, min: Option<i32>, max: Option<i32>) -> bool {
    match node {
        None => true,
        Some(n) => {
            if let Some(min_val) = min {
                if n.val <= min_val { return false; }
            }
            if let Some(max_val) = max {
                if n.val >= max_val { return false; }
            }
            is_bst(&n.left, min, Some(n.val)) && is_bst(&n.right, Some(n.val), max)
        }
    }
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 10,
        left: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
        right: Some(Box::new(TreeNode { val: 15, left: None, right: None })),
    }));
    println!("{}", is_bst(&root, None, None));
}

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Analyze tree structure

   The root node is 10, left child 5, right child 15. This satisfies BST property: 5 < 10 < 15.

2. Step 2: Trace is_bst function calls

   Function checks node values against min and max bounds recursively. All nodes satisfy constraints, so returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Tree is BST = true [OK]

Hint: Check node values within min/max bounds recursively [OK]

Common Mistakes:

• Ignoring min/max bounds in recursion
• Confusing <= and < in comparisons
• Assuming tree is not BST without checking children

4. Identify the bug in this Rust function that checks if a tree is a BST:

fn is_bst(node: &Option, min: Option<i32>, max: Option<i32>) -> bool {
    match node {
        None => true,
        Some(n) => {
            if let Some(min_val) = min {
                if n.val < min_val { return false; }
            }
            if let Some(max_val) = max {
                if n.val > max_val { return false; }
            }
            is_bst(&n.left, min, Some(n.val)) && is_bst(&n.right, Some(n.val), max)
        }
    }
}

medium

A. The function does not handle empty trees

B. The comparisons should use <= and >= instead of < and >

C. The recursion calls have wrong parameters order

D. The function should return i32 instead of bool

Solution

1. Step 1: Review comparison operators in BST validation

   BST requires node values to be strictly greater than min and strictly less than max, so using < and > is incorrect for duplicates.

2. Step 2: Correct comparison operators

   Comparisons should be <= min_val and >= max_val to reject equal values and maintain BST property.

3. Final Answer:

   The comparisons should use <= and >= instead of < and > -> Option B

4. Quick Check:

   Use <= and >= for BST checks [OK]

Hint: Use <= and >= to reject equal values in BST check [OK]

Common Mistakes:

• Using < and > allows duplicates breaking BST
• Mixing up parameter order in recursion
• Ignoring None case for empty trees

5. You have a binary tree where some nodes have duplicate values equal to their parent. You want to validate if it is a BST allowing duplicates only on the right subtree. How should you modify the Rust BST validation function?

hard

A. Disallow all duplicates by using strict < and > comparisons

B. Allow equal values only on the right by using n.val <= min_val for right subtree and n.val < max_val for left subtree

C. Allow equal values only when moving to the right subtree by changing comparison to n.val < min_val and n.val > max_val

D. Allow equal values only on the right by using n.val >= min_val for right subtree and n.val < max_val for left subtree

Solution

1. Step 1: Understand BST with duplicates on right

   Duplicates allowed only on right means left subtree nodes must be strictly less than current node, right subtree nodes can be equal or greater.

2. Step 2: Adjust min and max comparisons accordingly

   For left subtree, use n.val < max_val (strict less), for right subtree use n.val >= min_val (allow equal or greater).

3. Final Answer:

   Allow equal values only on the right by using n.val >= min_val for right subtree and n.val < max_val for left subtree -> Option D

4. Quick Check:

   Duplicates right subtree = n.val >= min_val [OK]

Hint: Allow equals only on right: use >= min_val, < max_val [OK]

Common Mistakes:

• Allowing duplicates on left subtree
• Using <= for left subtree allowing duplicates
• Not adjusting comparisons for duplicates