Why BST Property and Why It Matters in DSA Rust?

The Big Idea

What if you could find any number in a huge list without checking every single one?

The Scenario

Imagine you have a messy pile of books with no order. When you want a specific book, you have to search through every single one.

This is like storing numbers without any rule.

The Problem

Searching for a number in an unordered list means checking every item one by one.

This takes a lot of time and can be very tiring and slow.

The Solution

The BST property keeps numbers in order: left side has smaller numbers, right side has bigger numbers.

This order helps find numbers quickly by skipping large parts of the tree.

Before vs After

✗ Before

fn find_number(numbers: &[i32], target: i32) -> bool {
    for &num in numbers {
        if num == target {
            return true;
        }
    }
    false
}

✓ After

fn find_in_bst(node: &Option<Box<TreeNode>>, target: i32) -> bool {
    match node {
        None => false,
        Some(n) => {
            if target == n.value {
                true
            } else if target < n.value {
                find_in_bst(&n.left, target)
            } else {
                find_in_bst(&n.right, target)
            }
        }
    }
}

What It Enables

It enables fast searching, adding, and removing numbers by using the order to skip unnecessary checks.

Real Life Example

Think of a phone book sorted by names. You don't check every name; you jump to the right section quickly. BST property works the same way for numbers.

Key Takeaways

Without order, searching is slow and tiring.

BST property keeps data sorted to speed up operations.

This property is key for efficient searching and updating.

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