Validate if Tree is BST in DSA Rust - Execution Trace

Concept Flow - Validate if Tree is BST

Start at root node

↓

Check left subtree

↓

Is left subtree BST?

↓

Check right subtree

↓

Is right subtree BST?

↓

Check current node value

↓

Is current node value > max in left and < min in right?

↓

Return True

The flow checks recursively if left and right subtrees are BSTs and if current node value fits BST rules.

Execution Sample

DSA Rust

fn is_bst(node: &Option<Box<TreeNode>>, 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)
        }
    }
}

This function checks if a binary tree is a BST by verifying node values within min and max bounds recursively.

Execution Table

Step	Operation	Node Visited	Min Bound	Max Bound	Check Result	Tree State
1	Start at root	10	None	None	Continue	10 / \ 5 15
2	Check left subtree	5	None	10	Continue	5
3	Check left.left subtree	2	None	5	Continue	2
4	Check left.left.left subtree	None	None	2	True (empty)	None
5	Check left.left.right subtree	None	2	5	True (empty)	None
6	Check left.right subtree	7	5	10	Continue	7
7	Check left.right.left subtree	None	5	7	True (empty)	None
8	Check left.right.right subtree	None	7	10	True (empty)	None
9	Left subtree of root is BST	5	None	10	True	5 subtree OK
10	Check right subtree	15	10	None	Continue	15
11	Check right.left subtree	12	10	15	Continue	12
12	Check right.left.left subtree	None	10	12	True (empty)	None
13	Check right.left.right subtree	None	12	15	True (empty)	None
14	Check right.right subtree	20	15	None	Continue	20
15	Check right.right.left subtree	None	15	20	True (empty)	None
16	Check right.right.right subtree	None	20	None	True (empty)	None
17	Right subtree of root is BST	15	10	None	True	15 subtree OK
18	Check root node value	10	None	None	Valid	Root node OK
19	Final result	10	None	None	True	Whole tree is BST

💡 All nodes satisfy BST conditions, recursion ends with True.

Variable Tracker

Variable	Start	After Step 2	After Step 9	After Step 10	After Step 17	Final
node	root(10)	left(5)	left subtree done	right(15)	right subtree done	root(10)
min	None	None	None	Some(10)	Some(10)	None
max	None	Some(10)	Some(10)	None	None	None
check_result	N/A	Continue	True	Continue	True	True

Key Moments - 3 Insights

Why do we pass min and max bounds during recursion?

The min and max bounds ensure each node's value fits the BST rules relative to its ancestors, as shown in steps 2, 10, and 18 in the execution_table.

What happens when we reach a None node?

When a node is None (empty), it returns True immediately, meaning an empty subtree is valid. This is shown in steps 4, 5, 7, 8, 12, 13, 15, and 16.

Why do we check node.val <= min or >= max to return false?

Because BST requires left subtree nodes to be less than current node and right subtree nodes to be greater. Violating this breaks BST property, causing early return false as in steps 3 and 11 if conditions fail.

Visual Quiz - 3 Questions

Look at the execution_table, what is the min bound when visiting node 15 at step 10?

A Some(10)

B Some(5)

C None

D Some(15)

💡 Hint

Check the 'Min Bound' column at step 10 in execution_table.

At which step does the algorithm confirm the left subtree of root is a BST?

A Step 5

B Step 17

C Step 9

D Step 18

💡 Hint

Look for 'Left subtree of root is BST' in the 'Operation' column.

If the node value 7 was changed to 11, which step would fail the BST check?

A Step 11

B Step 6

C Step 3

D Step 18

💡 Hint

Check step 6 where node 7 is validated against max bound 10.

Concept Snapshot

Validate if Tree is BST:
- Recursively check left and right subtrees
- Pass min and max bounds to ensure node values fit BST rules
- Empty nodes return True
- Return False if node violates bounds
- Final True means tree is BST

Full Transcript

This visualization shows how to check if a binary tree is a BST by recursively verifying each node's value fits within min and max bounds passed down from ancestors. The process starts at the root, checks left subtree with updated max bound, then right subtree with updated min bound. Empty nodes return True. If any node violates the BST property by being less than or equal to min or greater than or equal to max, the function returns False immediately. The execution table traces each step visiting nodes, bounds checked, and partial results. The variable tracker shows how node, min, max, and check results change during recursion. Key moments clarify why bounds are needed and how empty nodes are handled. The quiz tests understanding of bounds and step outcomes. This method ensures the entire tree satisfies BST conditions.

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