Validate if Tree is BST in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BST Validation Function

What is the output of the following Rust code that checks if a binary tree is a valid BST?

DSA Rust

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

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

fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    fn helper(node: Option<Rc<RefCell<TreeNode>>>, min: Option<i32>, max: Option<i32>) -> bool {
        match node {
            None => true,
            Some(n) => {
                let n = n.borrow();
                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;
                    }
                }
                helper(n.left.clone(), min, Some(n.val)) && helper(n.right.clone(), Some(n.val), max)
            }
        }
    }
    helper(root, None, None)
}

fn main() {
    let node1 = Rc::new(RefCell::new(TreeNode { val: 1, left: None, right: None }));
    let node3 = Rc::new(RefCell::new(TreeNode { val: 3, left: None, right: None }));
    let node2 = Rc::new(RefCell::new(TreeNode { val: 2, left: Some(node1), right: Some(node3) }));

    println!("{}", is_valid_bst(Some(node2)));
}

A Compilation error

B false

C Runtime panic

D true

💡 Hint

Think about the BST property: left subtree values < node value < right subtree values.

The tree constructed is a valid BST with root 2, left child 1, and right child 3. The function correctly checks the BST property recursively and returns true.

❓ Predict Output

intermediate

Output of BST Validation with Invalid Tree

What is the output of the following Rust code that checks if a binary tree is a valid BST?

DSA Rust

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

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

fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    fn helper(node: Option<Rc<RefCell<TreeNode>>>, min: Option<i32>, max: Option<i32>) -> bool {
        match node {
            None => true,
            Some(n) => {
                let n = n.borrow();
                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;
                    }
                }
                helper(n.left.clone(), min, Some(n.val)) && helper(n.right.clone(), Some(n.val), max)
            }
        }
    }
    helper(root, None, None)
}

fn main() {
    let node1 = Rc::new(RefCell::new(TreeNode { val: 1, left: None, right: None }));
    let node4 = Rc::new(RefCell::new(TreeNode { val: 4, left: None, right: None }));
    let node3 = Rc::new(RefCell::new(TreeNode { val: 3, left: Some(node4), right: None }));
    let node2 = Rc::new(RefCell::new(TreeNode { val: 2, left: Some(node1), right: Some(node3) }));

    println!("{}", is_valid_bst(Some(node2)));
}

A false

B true

C Compilation error

D Runtime panic

💡 Hint

Check if the right child of node 3 violates BST rules.

Node 4 is in the left subtree of node 3 but has a value greater than 3, violating BST property. So the function returns false.

🔧 Debug

advanced

Identify the Bug in BST Validation Code

The following Rust function is intended to check if a binary tree is a valid BST. What is the bug causing incorrect results?

DSA Rust

fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    fn helper(node: Option<Rc<RefCell<TreeNode>>>, min: Option<i32>, max: Option<i32>) -> bool {
        match node {
            None => true,
            Some(n) => {
                let n = n.borrow();
                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;
                    }
                }
                helper(n.left.clone(), min, Some(n.val)) && helper(n.right.clone(), Some(n.val), max)
            }
        }
    }
    helper(root, None, None)
}

A The comparisons should use <= and >= instead of < and > to correctly enforce BST rules.

B The function should use a queue instead of recursion for traversal.

C The function should not clone nodes when calling helper recursively.

D The function should swap min and max parameters in recursive calls.

💡 Hint

Think about whether equal values are allowed in BST and how comparisons are made.

The bug is that the code uses < and > instead of <= and >=, so it allows equal values which violates strict BST property. Using <= and >= fixes this.

🧠 Conceptual

advanced

Why Use Min and Max Bounds in BST Validation?

Why does the BST validation function pass min and max bounds during recursion instead of just comparing child nodes to their parent?

A Because Rust requires explicit bounds for recursive functions.

B Because min and max bounds improve performance by avoiding recursion.

C Because nodes deeper in the tree must satisfy constraints from all ancestors, not just their immediate parent.

D Because comparing only to parent nodes causes runtime errors.

💡 Hint

Think about the BST property and how it applies to all nodes in the subtree.

BST property requires all nodes in left subtree to be less than the root and all nodes in right subtree to be greater than the root, so bounds from ancestors must be tracked.

🚀 Application

expert

Result of Inserting Nodes and Validating BST

Given the following Rust code that inserts nodes into a BST and then validates it, what is the printed output?

DSA Rust

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

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

fn insert(root: &mut Option<Rc<RefCell<TreeNode>>>, val: i32) {
    match root {
        None => {
            *root = Some(Rc::new(RefCell::new(TreeNode { val, left: None, right: None })));
        }
        Some(node) => {
            let mut n = node.borrow_mut();
            if val < n.val {
                insert(&mut n.left, val);
            } else {
                insert(&mut n.right, val);
            }
        }
    }
}

fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    fn helper(node: Option<Rc<RefCell<TreeNode>>>, min: Option<i32>, max: Option<i32>) -> bool {
        match node {
            None => true,
            Some(n) => {
                let n = n.borrow();
                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;
                    }
                }
                helper(n.left.clone(), min, Some(n.val)) && helper(n.right.clone(), Some(n.val), max)
            }
        }
    }
    helper(root, None, None)
}

fn main() {
    let mut root = None;
    insert(&mut root, 10);
    insert(&mut root, 5);
    insert(&mut root, 15);
    insert(&mut root, 6);
    insert(&mut root, 20);
    insert(&mut root, 4);

    println!("{}", is_valid_bst(root));
}

A false

B true

C Compilation error

D Runtime panic

💡 Hint

Check if the insert function maintains BST property and if validation matches.

The insert function correctly places nodes maintaining BST property. The validation confirms the tree is valid, so output is true.

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