BST Property and Why It Matters in DSA Rust - Execution Trace

Concept Flow - BST Property and Why It Matters

Start at root node

↓

Compare value to node

↓

Go left

↓

Repeat until leaf

↓

Insert or Search position found

The BST property guides traversal: smaller values go left, larger go right, ensuring ordered placement and fast search.

Execution Sample

DSA Rust

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

Checks if a binary tree follows BST property by verifying node values within allowed min/max ranges recursively.

Execution Table

Step	Operation	Node Visited	Min Allowed	Max Allowed	Check Result	Tree State
1	Start at root	10	None	None	Valid	10 / \ 5 15
2	Go left	5	None	10	Valid	10 / \ 5 15
3	Go left of 5	2	None	5	Valid	10 / \ 5 15 / 2
4	Left of 2 is None	None	None	2	Valid (leaf)	10 / \ 5 15 / 2
5	Right of 2 is None	None	2	5	Valid (leaf)	10 / \ 5 15 / 2
6	Back to 5, go right	7	5	10	Valid	10 / \ 5 15 / \ 2 7
7	Left of 7 is None	None	5	7	Valid (leaf)	10 / \ 5 15 / \ 2 7
8	Right of 7 is None	None	7	10	Valid (leaf)	10 / \ 5 15 / \ 2 7
9	Back to root, go right	15	10	None	Valid	10 / \ 5 15 / \ 2 7
10	Left of 15 is None	None	10	15	Valid (leaf)	10 / \ 5 15 / \ 2 7
11	Right of 15 is 20	20	15	None	Valid	10 / \ 5 15 / \ \ 2 7 20
12	Left of 20 is None	None	15	20	Valid (leaf)	10 / \ 5 15 / \ \ 2 7 20
13	Right of 20 is None	None	20	None	Valid (leaf)	10 / \ 5 15 / \ \ 2 7 20
14	All nodes valid	None	None	None	Tree is BST	10 / \ 5 15 / \ \ 2 7 20

💡 All nodes satisfy BST property within min/max bounds, traversal complete.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 6	After 9	Final
Current Node	10	5	2	None	7	15	20
Min Allowed	None	None	None	None	5	10	15
Max Allowed	None	10	5	2	10	None	None
Check Result	Valid	Valid	Valid	Valid (leaf)	Valid	Valid	Valid

Key Moments - 3 Insights

Why do we check if node value is strictly greater than min and less than max?

Because BST requires all left subtree nodes to be less than the current node and all right subtree nodes to be greater. The execution_table rows 3, 6, and 9 show these min/max bounds updating to enforce this.

What happens when we reach a None node?

Reaching None means a leaf's child, which is valid by definition. The execution_table rows 4, 5, 7, 8, 10, 12, and 13 show these leaf checks returning true.

Why do we pass updated min and max when going left or right?

To keep track of allowed value ranges for each subtree. For example, going left updates max to current node's value, ensuring no larger values appear left. This is shown in execution_table steps 2 and 9.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the min allowed value when visiting node 7?

A 10

B 5

C 2

D None

💡 Hint

Check the 'Min Allowed' column at step 6 in execution_table.

At which step does the traversal confirm the right subtree of node 15 is valid?

A Step 10

B Step 12

C Step 11

D Step 13

💡 Hint

Look at the 'Node Visited' column for node 20 in execution_table.

If node 7 had value 12 instead, which step would fail the BST check?

A Step 6

B Step 9

C Step 11

D Step 14

💡 Hint

Check step 6 where node 7 is compared against max allowed 10.

Concept Snapshot

BST Property:
- Left subtree nodes < current node
- Right subtree nodes > current node
- Use min/max bounds to check recursively
- Ensures fast search, insert, delete
- Violations break BST property
- Key for ordered tree operations

Full Transcript

This visualization shows how the BST property guides traversal and validation. Starting at the root, each node's value is checked to be within allowed min and max bounds. Left children must be less than the current node, right children greater. The recursive checks update these bounds as traversal proceeds. Leaf nodes (None) are valid by default. The execution table traces each node visit, the min/max constraints, and the validation result. The variable tracker shows how current node and bounds change step-by-step. Key moments clarify why bounds are strict and how None nodes are handled. The quiz tests understanding of min/max updates and failure points. This property is essential for BST operations to work efficiently.

Practice

1. What is the main property that defines a Binary Search Tree (BST)?

easy

A. For each node, all values in the left subtree are smaller, and all values in the right subtree are larger.

B. Each node has exactly two children.

C. All leaf nodes are at the same depth.

D. Nodes are arranged in a complete binary tree structure.

Solution

1. Step 1: Understand BST definition

   A BST requires that for every node, values in the left subtree are smaller and values in the right subtree are larger.

2. Step 2: Compare options to BST property

   For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. matches this definition exactly, while others describe different tree types or properties.

3. Final Answer:

   For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. -> Option A

4. Quick Check:

   BST property = For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. [OK]

Hint: Remember: left < node < right in BST [OK]

Common Mistakes:

• Confusing BST with complete binary tree
• Thinking all nodes must have two children
• Assuming leaf nodes must be at same depth

2. Which Rust code snippet correctly declares a BST node struct with optional left and right children?

easy

A. struct Node { value: i32, left: Option<Node>, right: Option<Node> }

B. struct Node { value: i32, left: Option, right: Option }

C. struct Node { value: i32, left: Box<Node>, right: Box<Node> }

D. struct Node { value: i32, left: Node, right: Node }

Solution

1. Step 1: Understand Rust ownership and recursive types

   Recursive structs in Rust must use Box to allocate on heap and Option for nullable children.

2. Step 2: Check each option

   struct Node { value: i32, left: Option, right: Option } uses Option correctly. Using Node directly or Option<Node> (without Box) causes infinite size. struct Node { value: i32, left: Box<Node>, right: Box<Node> } misses Option, so children can't be null.

3. Final Answer:

   struct Node { value: i32, left: Option, right: Option } -> Option B

4. Quick Check:

   Use Option for nullable recursive fields [OK]

Hint: Use Option for nullable recursive nodes in Rust [OK]

Common Mistakes:

• Omitting Option for nullable children
• Using Node directly causing infinite size error
• Not boxing recursive fields

3. Given the following Rust code inserting values into a BST, what is the in-order traversal output?

struct Node { value: i32, left: Option, right: Option }

fn insert(root: &mut Option, val: i32) {
    match root {
        None => *root = Some(Box::new(Node { value: val, left: None, right: None })),
        Some(node) => {
            if val < node.value {
                insert(&mut node.left, val);
            } else {
                insert(&mut node.right, val);
            }
        }
    }
}

fn inorder(root: &Option, vals: &mut Vec<i32>) {
    if let Some(node) = root {
        inorder(&node.left, vals);
        vals.push(node.value);
        inorder(&node.right, vals);
    }
}

fn main() {
    let mut root = None;
    insert(&mut root, 10);
    insert(&mut root, 5);
    insert(&mut root, 15);
    insert(&mut root, 7);
    let mut result = Vec::new();
    inorder(&root, &mut result);
    println!("{:?}", result);
}

medium

A. [5, 7, 10, 15]

B. [10, 5, 7, 15]

C. [15, 10, 7, 5]

D. [7, 5, 10, 15]

Solution

1. Step 1: Insert values into BST

   Insert 10 as root, 5 to left, 15 to right, 7 to right of 5.

2. Step 2: Perform in-order traversal

   In-order visits left subtree, node, then right subtree. So order is 5, 7, 10, 15.

3. Final Answer:

   [5, 7, 10, 15] -> Option A

4. Quick Check:

   In-order traversal of BST = sorted values [OK]

Hint: In-order traversal of BST gives sorted values [OK]

Common Mistakes:

• Confusing traversal order
• Inserting nodes incorrectly
• Assuming pre-order or post-order output

4. The following Rust function is intended to check if a tree is a valid BST. What is the bug?

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

medium

A. The function should return false when node is None.

B. The function does not handle empty trees correctly.

C. The min and max parameters are not updated correctly during recursion.

D. The comparison uses <= and >= instead of < and >, disallowing duplicate values.

Solution

1. Step 1: Analyze comparison operators

   The function uses <= and >= which disallow equal values, meaning duplicates are not allowed.

2. Step 2: Understand BST duplicate handling

   Some BST definitions allow duplicates on one side (usually right). Using strict < and > allows duplicates on one side.

3. Final Answer:

   The comparison uses <= and >= instead of < and >, disallowing duplicate values. -> Option D

4. Quick Check:

   Use < and > to allow duplicates in BST check [OK]

Hint: Use strict < and > to allow duplicates in BST check [OK]

Common Mistakes:

• Thinking None nodes cause errors
• Believing min/max are updated incorrectly
• Assuming empty tree is invalid

5. You want to find the kth smallest element in a BST efficiently. Which approach best uses the BST property to achieve this?

hard

A. Convert the BST to a sorted array and then access the kth element.

B. Perform a pre-order traversal and count nodes until k is reached.

C. Perform an in-order traversal and return the kth element visited.

D. Traverse the tree level by level until the kth node is found.

Solution

1. Step 1: Recall BST in-order traversal property

   In-order traversal visits nodes in ascending order due to BST property.

2. Step 2: Use in-order traversal to find kth smallest

   Counting nodes during in-order traversal lets you stop at kth smallest efficiently without extra sorting.

3. Final Answer:

   Perform an in-order traversal and return the kth element visited. -> Option C

4. Quick Check:

   In-order traversal gives sorted order, find kth element [OK]

Hint: Use in-order traversal to get sorted nodes and pick kth [OK]

Common Mistakes:

• Using pre-order or level-order which are not sorted
• Converting to array wastes extra space
• Not leveraging BST property for efficiency