BST Property and Why It Matters in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inorder Traversal on a BST

What is the output of the inorder traversal of this BST after inserting the values 10, 5, 15, 3, 7 in that order?

DSA Rust

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

impl Node {
    fn new(value: i32) -> Self {
        Node { value, left: None, right: None }
    }

    fn insert(&mut self, val: i32) {
        if val < self.value {
            match self.left {
                Some(ref mut left_node) => left_node.insert(val),
                None => self.left = Some(Box::new(Node::new(val))),
            }
        } else {
            match self.right {
                Some(ref mut right_node) => right_node.insert(val),
                None => self.right = Some(Box::new(Node::new(val))),
            }
        }
    }

    fn inorder(&self, vals: &mut Vec<i32>) {
        if let Some(ref left_node) = self.left {
            left_node.inorder(vals);
        }
        vals.push(self.value);
        if let Some(ref right_node) = self.right {
            right_node.inorder(vals);
        }
    }
}

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

A [3, 5, 7, 10, 15]

B [10, 5, 3, 7, 15]

C [15, 10, 7, 5, 3]

D [5, 3, 7, 10, 15]

💡 Hint

Remember that inorder traversal of a BST visits nodes in ascending order.

Inorder traversal visits the left subtree, then the node, then the right subtree. For a BST, this results in sorted order.

🧠 Conceptual

intermediate

Why Does BST Property Matter for Search?

Why is the BST property important for efficient searching in a binary search tree?

A It ensures that for any node, all values in the left subtree are smaller and all in the right subtree are larger, allowing binary search.

B It guarantees the tree is balanced, so search is always O(log n).

C It stores duplicate values only on the right subtree to avoid confusion.

D It allows nodes to have multiple parents for faster access.

💡 Hint

Think about how the tree structure helps decide which side to search next.

The BST property lets us decide to go left or right at each node based on comparison, enabling efficient binary search.

🔧 Debug

advanced

Identify the Bug Breaking BST Property

Which option shows a bug that breaks the BST property when inserting a new value?

DSA Rust

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

impl Node {
    fn insert(&mut self, val: i32) {
        if val <= self.value {
            match self.left {
                Some(ref mut left_node) => left_node.insert(val),
                None => self.left = Some(Box::new(Node { value: val, left: None, right: None })),
            }
        } else {
            match self.right {
                Some(ref mut right_node) => right_node.insert(val),
                None => self.right = Some(Box::new(Node { value: val, left: None, right: None })),
            }
        }
    }
}

A Change 'if val <= self.value' to 'if val < self.value' to avoid duplicates on left side.

B Change 'if val <= self.value' to 'if val > self.value' to insert larger values on left.

C Remove the 'if' condition and always insert on the right subtree.

D Change 'if val <= self.value' to 'if val >= self.value' to insert duplicates on right side.

💡 Hint

Check which option causes values to be inserted incorrectly breaking BST ordering.

Option B inserts larger values on the left subtree, which breaks the BST property that left subtree values must be smaller.

❓ Predict Output

advanced

Result of Deleting a Node with Two Children in BST

Given a BST with nodes 20, 10, 30, 5, 15, 25, 35, what is the inorder traversal after deleting node 20?

DSA Rust

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

impl Node {
    fn new(value: i32) -> Self {
        Node { value, left: None, right: None }
    }

    fn insert(&mut self, val: i32) {
        if val < self.value {
            match self.left {
                Some(ref mut left_node) => left_node.insert(val),
                None => self.left = Some(Box::new(Node::new(val))),
            }
        } else {
            match self.right {
                Some(ref mut right_node) => right_node.insert(val),
                None => self.right = Some(Box::new(Node::new(val))),
            }
        }
    }

    fn inorder(&self, vals: &mut Vec<i32>) {
        if let Some(ref left_node) = self.left {
            left_node.inorder(vals);
        }
        vals.push(self.value);
        if let Some(ref right_node) = self.right {
            right_node.inorder(vals);
        }
    }

    fn find_min(&self) -> i32 {
        match &self.left {
            Some(left_node) => left_node.find_min(),
            None => self.value,
        }
    }

    fn delete(self: Box<Self>, val: i32) -> Option<Box<Node>> {
        if val < self.value {
            let left = match self.left {
                Some(left_node) => left_node.delete(val),
                None => None,
            };
            Some(Box::new(Node { value: self.value, left, right: self.right }))
        } else if val > self.value {
            let right = match self.right {
                Some(right_node) => right_node.delete(val),
                None => None,
            };
            Some(Box::new(Node { value: self.value, left: self.left, right }))
        } else {
            if self.left.is_none() {
                return self.right;
            } else if self.right.is_none() {
                return self.left;
            } else {
                let min_val = self.right.as_ref().unwrap().find_min();
                let right = self.right.unwrap().delete(min_val);
                Some(Box::new(Node { value: min_val, left: self.left, right }))
            }
        }
    }
}

fn main() {
    let mut root = Node::new(20);
    root.insert(10);
    root.insert(30);
    root.insert(5);
    root.insert(15);
    root.insert(25);
    root.insert(35);

    let root_box = Box::new(root);
    let new_root = root_box.delete(20).unwrap();

    let mut result = Vec::new();
    new_root.inorder(&mut result);
    println!("{:?}", result);
}

A [5, 10, 15, 20, 25, 30, 35]

B [5, 10, 15, 25, 20, 30, 35]

C [5, 10, 15, 25, 30, 35]

D [10, 15, 25, 30, 35]

💡 Hint

When deleting a node with two children, replace it with the smallest value in the right subtree.

Deleting node 20 replaces it with 25 (smallest in right subtree). The inorder traversal reflects this replacement.

🧠 Conceptual

expert

Why Can BST Become Inefficient Without Balancing?

Why can a binary search tree become inefficient if it is not balanced?

A Because unbalanced trees do not maintain the BST property.

B Because balancing requires extra memory which slows down the tree.

C Because unbalanced trees cannot store duplicate values correctly.

D Because it can become a linked list in worst case, making search O(n) instead of O(log n).

💡 Hint

Think about the shape of the tree and how it affects search steps.

Without balancing, the tree can degenerate into a chain, making search linear time instead of logarithmic.

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