Why BST Over Plain Binary Tree in DSA Rust - Challenge Your Understanding

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why use a Binary Search Tree (BST) instead of a plain Binary Tree?

Which of the following best explains the main advantage of a Binary Search Tree (BST) over a plain Binary Tree?

A BSTs use less memory than plain Binary Trees because they store fewer nodes.

B BSTs keep elements sorted, allowing faster search, insert, and delete operations compared to plain Binary Trees.

C BSTs allow storing duplicate values easily, unlike plain Binary Trees.

D BSTs do not require pointers or references to child nodes, unlike plain Binary Trees.

💡 Hint

Think about how the order of elements affects searching speed.

A Binary Search Tree keeps its elements in sorted order, which allows operations like search, insert, and delete to be done efficiently, usually in O(log n) time. A plain Binary Tree has no order, so these operations can take longer, often O(n).

❓ Predict Output

intermediate

Output of Searching in BST vs Plain Binary Tree

Consider the following Rust-like pseudocode for searching a value in a tree. What is the output when searching for 7?

DSA Rust

enum TreeNode {
    Empty,
    Node(i32, Box<TreeNode>, Box<TreeNode>),
}

fn search_bst(node: &TreeNode, val: i32) -> bool {
    match node {
        TreeNode::Empty => false,
        TreeNode::Node(v, left, right) => {
            if *v == val {
                true
            } else if val < *v {
                search_bst(left, val)
            } else {
                search_bst(right, val)
            }
        }
    }
}

fn search_plain(node: &TreeNode, val: i32) -> bool {
    match node {
        TreeNode::Empty => false,
        TreeNode::Node(v, left, right) => {
            if *v == val {
                true
            } else {
                search_plain(left, val) || search_plain(right, val)
            }
        }
    }
}

// Tree structure for BST:
//       5
//      / \
//     3   8
//        / \
//       7  10

// Tree structure for plain binary tree:
//       5
//      / \
//     8   3
//    / \
//   7  10

// What is the output of search_bst(root_bst, 7) and search_plain(root_plain, 7)?

A search_bst: true, search_plain: false

B search_bst: false, search_plain: true

C search_bst: true, search_plain: true

D search_bst: false, search_plain: false

💡 Hint

Both trees contain the value 7, but their structure differs.

Both search functions correctly find 7 in their respective trees. The BST search uses ordering to decide which branch to search, while the plain tree search checks both branches recursively.

🔧 Debug

advanced

Why does this BST insertion code fail to keep the tree sorted?

Examine the Rust-like code below for inserting a value into a BST. What is the main reason it fails to maintain BST properties?

DSA Rust

fn insert_bst(node: &mut TreeNode, val: i32) {
    match node {
        TreeNode::Empty => {
            *node = TreeNode::Node(val, Box::new(TreeNode::Empty), Box::new(TreeNode::Empty));
        }
        TreeNode::Node(v, left, right) => {
            if val <= *v {
                insert_bst(left, val);  // <-- Problem here
            } else {
                insert_bst(right, val);
            }
        }
    }
}

A The code inserts smaller or equal values into the right subtree and larger values into the left subtree, reversing BST rules.

B The code does not handle the Empty node case, causing runtime errors.

C The code uses immutable references, so it cannot modify the tree nodes.

D The code inserts values only at the root, never descending the tree.

💡 Hint

Check which subtree the code inserts smaller and larger values into.

In a BST, smaller or equal values go to the left subtree, larger values to the right. This code swaps them, breaking the BST property.

📝 Syntax

advanced

Identify the syntax error in this Rust BST traversal code

Which option correctly fixes the syntax error in the following Rust-like code for inorder traversal of a BST?

DSA Rust

fn inorder(node: &TreeNode) {
    match node {
        TreeNode::Empty => (),
        TreeNode::Node(v, left, right) => {
            inorder(left);
            println!("{}", v);
            inorder(right);
        }
    }
}

A Replace match with if let syntax.

B Remove the parentheses after TreeNode::Empty.

C Change println! macro to print! macro.

D Add semicolons after inorder(left) and println!("{}", v) calls.

💡 Hint

Rust requires statements to end with semicolons unless they are the last expression.

Missing semicolons after function calls cause syntax errors. Adding them fixes the code.

🚀 Application

expert

How many nodes are in a perfectly balanced BST of height 3?

Consider a perfectly balanced Binary Search Tree of height 3 (root at height 1). How many nodes does it contain?

A 7

B 8

C 15

D 31

💡 Hint

Recall the formula for the number of nodes in a perfect binary tree: 2^height - 1.

A perfectly balanced binary tree of height h has 2^h - 1 nodes. For height 3, nodes = 2^3 - 1 = 7.

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