Validate if Tree is BST in DSA Rust - Build from Scratch

Validate if Tree is BST

📖 Scenario: You are working with a simple binary tree structure in Rust. Your task is to check if this tree follows the rules of a Binary Search Tree (BST). A BST is a tree where for every node, all values in the left subtree are smaller, and all values in the right subtree are larger.This is important because BSTs allow fast searching, like looking up a word in a dictionary quickly.

🎯 Goal: You will build a Rust program that creates a binary tree, sets up helper variables, writes the logic to check if the tree is a BST, and finally prints the result.

📋 What You'll Learn

Create a binary tree using the provided TreeNode struct with exact values

Add helper variables to assist in the BST validation

Write a recursive function is_bst that checks if the tree is a BST

Print true if the tree is a BST, otherwise false

💡 Why This Matters

🌍 Real World

Binary Search Trees are used in databases and file systems to quickly find, insert, or delete data.

💼 Career

Understanding BST validation is important for software engineers working with data structures, algorithms, and performance optimization.

1

Create the binary tree

Create a binary tree using the TreeNode struct with this exact structure:
root node with value 10, left child with value 5, and right child with value 15. The left child has no children, and the right child has a right child with value 20 and no left child.

DSA Rust

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

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

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn main() {
    // Create the binary tree with root value 10, left child 5, right child 15, and right child's right child 20
    // Your code here
}

Hint

Use Rc::new(RefCell::new(TreeNode::new(value))) to create nodes. Connect children by setting left and right fields inside borrow_mut().

2

Add helper variables for BST validation

Add two variables min_val and max_val of type Option and set both to None. These will help track the allowed value range during BST validation.

DSA Rust

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

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

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn main() {
    let root = Rc::new(RefCell::new(TreeNode::new(10)));
    let left_child = Rc::new(RefCell::new(TreeNode::new(5)));
    let right_child = Rc::new(RefCell::new(TreeNode::new(15)));
    let right_right_child = Rc::new(RefCell::new(TreeNode::new(20)));

    right_child.borrow_mut().right = Some(right_right_child);
    root.borrow_mut().left = Some(left_child);
    root.borrow_mut().right = Some(right_child);

    // Add min_val and max_val variables set to None
    // Your code here
}

Hint

Use let min_val: Option = None; and let max_val: Option = None; to create the helper variables.

3

Write the BST validation function

Write a recursive function is_bst that takes node: Option>>, min_val: Option, and max_val: Option as parameters and returns bool. It should check if the tree rooted at node is a BST by ensuring the node's value is greater than min_val and less than max_val, and recursively check left and right subtrees with updated ranges.

DSA Rust

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

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

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn is_bst(node: Option>>, min_val: Option, max_val: Option) -> bool {
    // Implement the BST check logic here
    // Your code here
}

fn main() {
    let root = Rc::new(RefCell::new(TreeNode::new(10)));
    let left_child = Rc::new(RefCell::new(TreeNode::new(5)));
    let right_child = Rc::new(RefCell::new(TreeNode::new(15)));
    let right_right_child = Rc::new(RefCell::new(TreeNode::new(20)));

    right_child.borrow_mut().right = Some(right_right_child);
    root.borrow_mut().left = Some(left_child);
    root.borrow_mut().right = Some(right_child);

    let min_val: Option = None;
    let max_val: Option = None;
}

Hint

Use match to handle None and Some. Check if val is within min_val and max_val. Recursively call is_bst on left and right children with updated ranges.

4

Print the BST validation result

Call the is_bst function with root, min_val, and max_val and print the result using println!.

DSA Rust

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

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

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn is_bst(node: Option>>, min_val: Option, max_val: Option) -> bool {
    match node {
        None => true,
        Some(n) => {
            let n_borrow = n.borrow();
            let val = n_borrow.val;

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

            is_bst(n_borrow.left.clone(), min_val, Some(val)) &&
            is_bst(n_borrow.right.clone(), Some(val), max_val)
        }
    }
}

fn main() {
    let root = Rc::new(RefCell::new(TreeNode::new(10)));
    let left_child = Rc::new(RefCell::new(TreeNode::new(5)));
    let right_child = Rc::new(RefCell::new(TreeNode::new(15)));
    let right_right_child = Rc::new(RefCell::new(TreeNode::new(20)));

    right_child.borrow_mut().right = Some(right_right_child);
    root.borrow_mut().left = Some(left_child);
    root.borrow_mut().right = Some(right_child);

    let min_val: Option = None;
    let max_val: Option = None;

    // Call is_bst and print the result
    // Your code here
}

Hint

Call is_bst(Some(root), min_val, max_val) and print the result with println!.

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