Why BST Over Plain Binary Tree in DSA Rust - See It Work

Why BST Over Plain Binary Tree

📖 Scenario: Imagine you have a collection of numbers and want to find, add, or check if a number exists quickly. You can store them in a simple tree or a special tree called a Binary Search Tree (BST).This project will help you see why BST is better than a plain binary tree for searching numbers.

🎯 Goal: You will create two trees: a plain binary tree and a binary search tree (BST). Then, you will search for a number in both trees and see the difference in how they work.

📋 What You'll Learn

Create a plain binary tree with specific numbers

Create a binary search tree (BST) with the same numbers

Write a function to search for a number in the plain binary tree

Write a function to search for a number in the BST

Print the search results for both trees

💡 Why This Matters

🌍 Real World

Binary search trees are used in databases, file systems, and many software tools to quickly find, add, or remove data.

💼 Career

Understanding BSTs helps in software development roles that require efficient data storage and retrieval, such as backend development and systems programming.

1

Create a Plain Binary Tree

Create a struct called Node with fields value: i32, left: Option, and right: Option. Then create a plain binary tree with root value 10, left child 5, and right child 15.

DSA Rust

// Define struct Node
// Create a plain binary tree with root 10, left child 5, right child 15
// Your code here

Hint

Use Option> for left and right children to allow empty branches.

2

Create a Binary Search Tree (BST)

Create a function called insert_bst that takes a mutable reference to an Option<Box<Node>> and a value i32. Insert the value into the BST following BST rules. Then create a BST by inserting values 10, 5, and 15 into an empty tree.

DSA Rust

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

fn insert_bst(root: &mut Option>, val: i32) {
    // Your code here
}

fn main() {
    let mut bst_root: Option> = None;
    // Insert 10, 5, 15 into bst_root
    // Your code here
}

Hint

Use recursion to insert values in the correct place following BST rules.

3

Search for a Value in Both Trees

Create two functions: search_plain and search_bst. Both take a reference to Option<Box<Node>> and a value i32. search_plain searches the plain binary tree by checking all nodes. search_bst searches the BST using BST rules. Return true if found, false otherwise.

DSA Rust

fn search_plain(root: &Option>, val: i32) -> bool {
    // Your code here
}

fn search_bst(root: &Option>, val: i32) -> bool {
    // Your code here
}

fn main() {
    // Existing code
}

Hint

Use recursion to check nodes in plain tree and use BST rules for BST search.

4

Print Search Results for Both Trees

In main, print the result of searching for 15 in the plain binary tree using search_plain and in the BST using search_bst. Use println!("Plain tree found: {}", result) and println!("BST found: {}", result).

DSA Rust

fn main() {
    // Existing code
    // Print search results for value 15 in plain_root and bst_root
    // Your code here
}

Hint

Wrap plain_root in Some(Box::new()) to call search_plain.

Practice

1. Why is a Binary Search Tree (BST) preferred over a plain Binary Tree for searching operations?

easy

A. Because BST nodes can have more than two children

B. Because BST uses less memory than a plain Binary Tree

C. Because BST does not require pointers to child nodes

D. Because BST keeps elements in sorted order, allowing faster search

Solution

1. Step 1: Understand the structure difference

   A plain Binary Tree has no order, so searching requires checking many nodes.

2. Step 2: Analyze BST property

   BST keeps nodes sorted: left child smaller, right child larger, enabling binary search.

3. Final Answer:

   Because BST keeps elements in sorted order, allowing faster search -> Option D

4. Quick Check:

   Sorted structure = faster search [OK]

Hint: BST sorts nodes to speed up search [OK]

Common Mistakes:

• Thinking BST uses less memory
• Confusing number of children per node
• Assuming BST has no pointers

2. Which of the following is the correct Rust syntax to declare a node in a Binary Search Tree?

easy

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

B. struct Node { value: i32, left: Option, right: Option }

C. struct Node { value: i32, left: &Node, right: &Node }

D. struct Node { value: i32, left: Node, right: Node }

Solution

1. Step 1: Understand Rust ownership for trees

   Nodes must use Option for left and right to allow null and ownership.

2. Step 2: Check each option

   struct Node { value: i32, left: Option, right: Option } uses Option, correct for nullable child nodes. Others miss Option or use references incorrectly.

3. Final Answer:

   struct Node { value: i32, left: Option, right: Option } -> Option B

4. Quick Check:

   Nullable boxed children = struct Node { value: i32, left: Option, right: Option } [OK]

Hint: Use Option for nullable children in Rust [OK]

Common Mistakes:

• Omitting Option causing no null children
• Using references without lifetimes
• Using Box without Option causing no empty child

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) {
    if let Some(node) = root {
        if val < node.value {
            insert(&mut node.left, val);
        } else {
            insert(&mut node.right, val);
        }
    } else {
        *root = Some(Box::new(Node { value: val, left: None, right: None }));
    }
}

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, root, right: nodes visited in order 5, 7, 10, 15.

3. Final Answer:

   [5, 7, 10, 15] -> Option A

4. Quick Check:

   In-order traversal = sorted values [OK]

Hint: In-order traversal of BST gives sorted values [OK]

Common Mistakes:

• Confusing traversal order
• Inserting nodes incorrectly
• Misreading left/right child placement

4. The following Rust code attempts to insert a value into a BST but causes a compile error. What is the error?

fn insert(root: &Option, val: i32) {
    if let Some(node) = root {
        if val < node.value {
            insert(&node.left, val);
        } else {
            insert(&node.right, val);
        }
    } else {
        *root = Some(Box::new(Node { value: val, left: None, right: None }));
    }
}

medium

A. Recursive call causes stack overflow

B. Missing lifetime annotations for references

C. Cannot assign to `*root` because `root` is an immutable reference

D. Node struct is not defined

Solution

1. Step 1: Check parameter mutability

   Function takes `root` as immutable reference `&Option`, so cannot modify it.

2. Step 2: Identify assignment error

   Line `*root = Some(...)` tries to assign through immutable reference, causing compile error.

3. Final Answer:

   Cannot assign to `*root` because `root` is an immutable reference -> Option C

4. Quick Check:

   Mutable reference needed for assignment [OK]

Hint: Use &mut for parameters you want to change [OK]

Common Mistakes:

• Using & instead of &mut for mutable access
• Ignoring compiler error messages
• Assuming recursive calls cause stack overflow here

5. You want to store a large set of unique numbers and perform fast search, insert, and delete operations. Why is a BST a better choice than a plain Binary Tree, and what is the average time complexity for these operations in a balanced BST?

hard

A. BST keeps data sorted, enabling O(log n) average time for search, insert, and delete

B. BST uses less memory and has O(1) time for all operations

C. Plain Binary Tree is better because it allows faster insertions

D. BST allows multiple children per node, improving speed

Solution

1. Step 1: Compare data organization

   BST keeps nodes sorted, unlike plain Binary Tree which has no order.

2. Step 2: Analyze operation time complexity

   Balanced BST operations (search, insert, delete) take O(log n) on average due to tree height.

3. Final Answer:

   BST keeps data sorted, enabling O(log n) average time for search, insert, and delete -> Option A

4. Quick Check:

   Sorted structure + balanced height = O(log n) [OK]

Hint: Balanced BST gives O(log n) for main operations [OK]

Common Mistakes:

• Assuming O(1) time for BST operations
• Confusing plain Binary Tree with BST
• Thinking BST nodes have multiple children