BST Property and Why It Matters in DSA Rust - Build from Scratch

BST Property and Why It Matters

📖 Scenario: Imagine you are organizing books on a shelf by their unique ID numbers. You want to keep the shelf sorted so you can quickly find any book. This is similar to how a Binary Search Tree (BST) keeps data organized.

🎯 Goal: You will create a simple Binary Search Tree node structure in Rust, add values following the BST property, and then print the tree in order to see the sorted values.

📋 What You'll Learn

Create a BST node struct with integer value and optional left and right children

Create a root node with a specific value

Add two child nodes following the BST property: left child less than root, right child greater than root

Print the values of the BST in sorted order using in-order traversal

💡 Why This Matters

🌍 Real World

Binary Search Trees are used in databases, file systems, and many software systems to keep data sorted and allow fast searching.

💼 Career

Understanding BSTs is important for software engineers, especially those working with data structures, algorithms, and performance optimization.

1

Create the BST Node Structure

Create a struct called BSTNode with a field value of type i32, and two optional boxed children called left and right of type Option>.

DSA Rust

# Define the BSTNode struct with value, left, and right fields
# Your code here

Hint

Use struct BSTNode with fields value: i32, left: Option>, and right: Option>.

2

Create the Root Node

Create a variable called root of type BSTNode with value set to 10, and both left and right set to None.

DSA Rust

struct BSTNode {
    value: i32,
    left: Option>,
    right: Option>,
}

// Create the root node with value 10
# Your code here

Hint

Use let root = BSTNode { value: 10, left: None, right: None }; inside fn main().

3

Add Left and Right Child Nodes Following BST Property

Inside fn main(), create two variables: left_child with value 5 and right_child with value 15, both with left and right set to None. Then create a new root node with value 10, left set to Some(Box::new(left_child)), and right set to Some(Box::new(right_child)).

DSA Rust

struct BSTNode {
    value: i32,
    left: Option>,
    right: Option>,
}

fn main() {
    // Create left_child with value 5 and right_child with value 15
    // Create root with left and right children
    # Your code here
}

Hint

Create left_child and right_child with values 5 and 15, then assign them as boxed children of root.

4

Print the BST Values In-Order

Write a function called in_order that takes a reference to a BSTNode and prints the values in sorted order using in-order traversal. Then call in_order(&root) inside fn main().

DSA Rust

struct BSTNode {
    value: i32,
    left: Option>,
    right: Option>,
}

// Define in_order function here
# Your code here

fn main() {
    let left_child = BSTNode {
        value: 5,
        left: None,
        right: None,
    };
    let right_child = BSTNode {
        value: 15,
        left: None,
        right: None,
    };
    let root = BSTNode {
        value: 10,
        left: Some(Box::new(left_child)),
        right: Some(Box::new(right_child)),
    };

    // Call in_order function here
    # Your code here
}

Hint

Use recursion to visit left child, print current node value, then visit right child. Call in_order(&root) in main.

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