Why BST Over Plain Binary Tree in DSA Rust - Quick Recap

Recall & Review

beginner

What is the main difference between a Binary Search Tree (BST) and a plain Binary Tree?

A BST keeps its nodes in a sorted order where left child nodes are smaller and right child nodes are larger than the parent, while a plain Binary Tree has no such order.

beginner

Why is searching faster in a BST compared to a plain Binary Tree?

Because BSTs keep nodes sorted, you can decide to go left or right at each step, reducing the search space by half each time, unlike a plain Binary Tree where you might have to check every node.

intermediate

How does the structure of a BST help in efficient insertion and deletion?

Insertion and deletion in a BST maintain the sorted order by placing or removing nodes in a way that keeps left children smaller and right children larger, allowing these operations to be done quickly compared to an unordered tree.

beginner

What is a real-life analogy for why BSTs are preferred over plain Binary Trees?

Think of a phone book sorted by names (BST) versus a pile of unsorted papers (plain Binary Tree). Finding a name in the sorted phone book is much faster because you know where to look.

intermediate

What happens to BST performance if the tree becomes unbalanced?

If a BST becomes unbalanced (like a linked list), its operations can degrade to linear time, losing the speed advantage over a plain Binary Tree.

What property does a Binary Search Tree maintain that a plain Binary Tree does not?

A Nodes are sorted so left child < parent < right child

B Each node has exactly two children

C Nodes store only numbers

D All leaf nodes are at the same level

BSTs maintain the sorted order property where left child nodes are smaller and right child nodes are larger than the parent.

Why is searching in a BST generally faster than in a plain Binary Tree?

A Because BSTs use hashing internally

B Because BSTs have fewer nodes

C Because BSTs are sorted, allowing binary search-like steps

D Because BSTs store data in arrays

BSTs allow you to decide to go left or right based on comparison, reducing search space quickly.

What can cause a BST to lose its performance advantage?

A If it has too many leaf nodes

B If it becomes unbalanced and resembles a linked list

C If it stores strings instead of numbers

D If it uses recursion

An unbalanced BST can degrade to linear time operations, losing its speed benefits.

Which operation benefits from the BST's sorted structure?

A Insertion

B Printing nodes in any order

C Counting nodes

D Storing duplicate values

Insertion in BST places nodes to maintain sorted order, making it efficient.

What is a simple analogy to understand why BSTs are better than plain Binary Trees?

A A car vs. a bicycle

B A basket of mixed fruits vs. a basket of apples

C A bookshelf vs. a table

D A sorted phone book vs. a pile of unsorted papers

A sorted phone book lets you find names quickly, similar to how BSTs speed up search.

Explain why a Binary Search Tree is preferred over a plain Binary Tree for searching data.

Think about how you find a word in a dictionary.

Describe what happens to BST operations when the tree becomes unbalanced and why it matters.

Imagine a tree that looks like a chain.

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