Validate if Tree is BST in DSA Rust - Deep Dive

Overview - Validate if Tree is BST

What is it?

Given a binary tree, determine whether it is a valid Binary Search Tree (BST). A BST requires: (1) every node in the left subtree has a value strictly less than the node's value, and (2) every node in the right subtree has a value strictly greater than the node's value. Both conditions must hold for every node, not just immediate children.

Why it matters

BST validation is a fundamental interview problem that tests understanding of recursive tree reasoning and the propagation of constraints down subtrees. The key insight — that constraints from ancestors must be passed down — is a pattern used in tree DP, segment tree lazy propagation, and constraint propagation algorithms.

Where it fits

You need comfort with Rust's recursive tree representation using Option> and recursive pattern matching before tackling this. After mastering it, BST insert/delete/search, kth smallest in BST, and inorder successor follow naturally.

Mental Model

Core Idea

Each node has a valid value range determined by its ancestors. Root can be anything (−∞ to +∞). Left child must be less than parent and within parent's lower bound. Right child must be greater than parent and within parent's upper bound.

Think of it like...

Imagine each node as a gatekeeper with a permitted range. Root permits all values. Going left narrows the upper bound to the parent's value. Going right narrows the lower bound. Every node must fit within the range its ancestors permit — not just be less/greater than its direct parent.

        10
       /  \
      5    15
     / \   / \
    3   7 12  20

Valid BST. Constraint propagation:
  Root 10: range (-∞, +∞)
  Left 5:  range (-∞, 10)  ← upper bound = 10
  Right 15: range (10, +∞) ← lower bound = 10
  Left-Left 3: range (-∞, 5) ← upper = 5
  Left-Right 7: range (5, 10) ← lower=5, upper=10
  Right-Left 12: range (10, 15) ← lower=10, upper=15 ✓

Build-Up - 5 Steps

1

Foundation

The Common Mistake — Checking Only Parent

Concept: Checking node.val > node.left.val is insufficient — constraints from grandparents must be honored too.

Consider tree: root=10, left=5, left.right=7, left.right.right=12. Each node looks locally valid (7>5, 12>7), but 12 > root(10) — it should be in the right subtree. Checking only immediate parent misses this. The fix: pass min and max bounds through the recursion.

Result

Local parent check is necessary but not sufficient. Global bounds must be propagated.

Every node has TWO constraints: it must be greater than the maximum in its left subtree AND less than the minimum in its right subtree. Ancestor constraints propagate these bounds.

2

Foundation

Recursive Validation with Bounds

Concept: Pass (min_bound, max_bound) through recursion. Each node's value must be strictly within these bounds.

fn is_valid(node: &Option>, min: Option, max: Option) -> bool { match node { None => true, Some(n) => { if let Some(lo) = min { if n.val <= lo { return false; } } if let Some(hi) = max { if n.val >= hi { return false; } } is_valid(&n.left, min, Some(n.val)) && is_valid(&n.right, Some(n.val), max) } } }. Use Option for bounds to handle i32::MIN and i32::MAX edge cases without special sentinels.

Result

O(n) time, O(h) space (recursion stack) validation covering all global constraints.

Using Option instead of i64 or sentinel values is idiomatic Rust — None means 'no bound', Some(x) means 'bounded by x'.

3

Intermediate

Inorder Traversal Approach

🤔Before reading on: inorder traversal of a BST produces what kind of sequence? Commit to your answer.

Concept: Inorder traversal of a valid BST produces strictly ascending values. Check if inorder sequence is strictly increasing.

Traverse the tree inorder (left → root → right). For a valid BST, each visited node's value must be strictly greater than the previously visited node's value. In Rust: use a mutable reference to track the previous value: fn inorder(node: &Option>, prev: &mut Option) -> bool. Update prev after visiting each node. If any node violates strict ordering, return false.

Result

Alternative O(n) time, O(h) space validation using inorder property.

The inorder approach is intuitive and easy to implement. The bounds approach is slightly more efficient (returns false immediately without full traversal) and handles edge cases more explicitly.

4

Intermediate

Edge Cases — i32::MIN/MAX and Equal Values

🤔Before reading on: if a node has value i32::MIN, can we use i32::MIN-1 as the lower bound sentinel? Commit to your answer.

Concept: BST validation must handle i32::MIN and i32::MAX as valid node values without sentinel overflow.

If we use i32::MIN-1 as 'no lower bound', that overflows in Rust debug mode. Use Option: None means unbounded, Some(x) means bounded by x. Strict inequality: node.val > min.unwrap() and node.val < max.unwrap(). A BST requires STRICT inequality — equal values are invalid.

Result

Correct handling of boundary values without integer overflow.

Using Option for bounds is the Rust-idiomatic solution to the sentinel value problem — it's more expressive than magic numbers and avoids overflow.

5

Advanced

Iterative Inorder with Stack

🤔Before reading on: can you validate a BST without recursion using an explicit stack? Commit yes or no.

Concept: Use an explicit stack to simulate inorder traversal iteratively.

Initialize stack = vec![], current = &root, prev: Option = None. While current.is_some() or stack non-empty: push left spine onto stack. Pop a node: compare val with prev (must be strictly greater). Update prev. Move to right child. In Rust with Option>, this requires immutable references to avoid ownership issues — use &Option> throughout.

Result

O(n) time, O(h) space iterative validation without recursion overhead.

Iterative inorder avoids stack overflow for very deep trees. In Rust, borrowing makes the iterative approach slightly more verbose than in other languages — immutable references throughout prevent ownership issues.

Under the Hood

The recursive bounds approach works by propagating constraints: going left tightens the upper bound (max = current node's value); going right tightens the lower bound (min = current node's value). Every node checks both bounds. At each node, the left subtree inherits the current bounds with max updated, and the right subtree inherits bounds with min updated. The recursion visits each node exactly once — O(n).

Why designed this way?

The bounds approach is more efficient than inorder traversal because it can return false immediately when a violation is detected, without completing the traversal. The inorder approach is simpler to reason about. Both are correct and O(n) worst-case.

Constraint propagation for BST check:

        10
       /  \
      5    15
     / \
    3   12 ← INVALID: 12 > 10 (root's upper bound)

Recursive calls:
check(10, None, None) → OK, check children
check(5, None, Some(10)) → OK
check(3, None, Some(5)) → OK
check(12, Some(5), Some(10)) → 12 >= 10 → FALSE ✓ caught

Myth Busters - 2 Common Misconceptions

Quick: is it sufficient to check that each node is greater than its left child and less than its right child? Commit yes or no.

Common Belief: Checking node > left_child and node < right_child for every node validates a BST.

Reality: This only checks immediate children, missing violations from grandparent constraints. A node in the right subtree of the root must be greater than the root, not just its direct parent.

Why it matters: The most common BST validation bug — always propagate ancestor bounds, not just parent values.

Quick: does a valid BST allow equal values (node.val == left_child.val)? Commit yes or no.

Common Belief: BST allows values equal to the parent in either subtree.

Reality: A valid BST requires STRICT inequality: left subtree values strictly less than node, right subtree values strictly greater. Equal values make it invalid.

Why it matters: Using >= instead of > in the bound check produces false positives — trees with duplicates appear valid when they're not.

Expert Zone

1

For trees with i64 values instead of i32, the Option bounds approach works unchanged — no sentinel modifications needed.

2

The Morris traversal technique validates a BST in O(n) time and O(1) space (no recursion stack, no explicit stack) by temporarily modifying tree structure — advanced but interview-worthy.

3

In competitive Rust, tree nodes are often represented as Vec with index-based children — the same bounds propagation applies with array indices instead of Box pointers.

When NOT to use

If you only need to check one subtree or partial validation, the inorder approach may be cleaner since you can stop early with an iterator. For very deep trees (near stack overflow depth), use the iterative inorder approach.

Production Patterns

BST validation appears in: database B-tree integrity checks, compiler symbol table verification, ordered index validation, and game tree pruning validation (alpha-beta bounds). The constraint propagation pattern appears broadly in constraint satisfaction problems (CSP) and backtracking algorithms.

Connections

Inorder Traversal of BST

Inorder traversal of a BST produces sorted output — BST validation's inorder approach directly exploits this property.

The connection between BST structure and inorder sorted output is foundational. Every BST property can be expressed in terms of inorder sequence.

Kth Smallest Element in BST

Both use inorder traversal of BST — validation checks strict monotone increase, kth smallest counts to the kth node.

Mastering BST validation's inorder approach makes kth smallest trivial — same traversal, different stopping condition.

Common Pitfalls

#1 Checking only parent vs child, missing grandparent constraint violations.

Wrong approach:

fn is_bst(node: &Option>) -> bool {
match node {
None => true,
Some(n) => {
// WRONG: only checks immediate children
let left_ok = n.left.as_ref().map_or(true, |l| l.val < n.val);
let right_ok = n.right.as_ref().map_or(true, |r| r.val > n.val);
left_ok && right_ok && is_bst(&n.left) && is_bst(&n.right)
}
}
}

Correct approach:

fn is_bst_helper(node: &Option>, min: Option, max: Option) -> bool {
match node {
None => true,
Some(n) => {
if min.map_or(false, |lo| n.val <= lo) { return false; }
if max.map_or(false, |hi| n.val >= hi) { return false; }
is_bst_helper(&n.left, min, Some(n.val)) &&
is_bst_helper(&n.right, Some(n.val), max)
}
}
}

Root cause:

Checking only immediate parent misses the global BST constraint. A node can be locally valid but globally invalid if it violates an ancestor's bound.

#2 Using i32::MIN and i32::MAX as sentinels causing overflow in Rust debug mode.

Wrong approach:

fn is_bst(node: &Option>, min: i32, max: i32) -> bool {
// RISK: calling with i32::MIN - 1 causes overflow panic in debug
is_bst(&n.left, min, n.val) // may overflow if n.val == i32::MIN
}

Correct approach:

fn is_bst(node: &Option>, min: Option, max: Option) -> bool {
// None means unbounded — no overflow possible
is_bst(&n.left, min, Some(n.val)) // Some(n.val) regardless of n.val's value
}

Root cause:

Using integer sentinels (i32::MIN-1) overflows in Rust's debug mode. Option is the correct Rust idiom for optional bounds.

Key Takeaways

Always propagate ancestor bounds — checking only parent vs child misses the most common test case (a right subtree node smaller than the root).

Use Option for bounds in Rust — None means unbounded, Some(x) means bounded. Avoids sentinel overflow on i32::MIN/MAX.

BST requires STRICT inequality — equal values make the tree invalid.

Inorder traversal of a valid BST produces strictly ascending values — an alternative O(n) validation approach.

Recursive bounds approach can return false immediately on first violation; inorder must traverse more before detecting a violation deep in the tree.

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