Why BST Over Plain Binary Tree in DSA Rust - Why It Works

Concept Flow - Why BST Over Plain Binary Tree

Start with Plain Binary Tree

↓

Insert nodes anywhere

↓

No order: left/right child any value

↓

Search: must check all nodes

↓

Time: O(n) worst case

↓

Switch to BST

↓

Insert nodes with order: left < parent < right

↓

Search: go left or right based on value

↓

Time: O(log n) average

↓

More efficient search, insert, delete

Shows how a plain binary tree inserts nodes without order causing slow search, while BST keeps order for faster search.

Execution Sample

DSA Rust

Insert 10
Insert 5
Insert 15
Search 5
Search 20

Inserts nodes in BST order and searches values, showing efficient path.

Execution Table

Step	Operation	Nodes in Tree	Pointer Changes	Visual State
1	Insert 10	10	root = 10	10
2	Insert 5	10, 5	10.left = 5	10 / 5
3	Insert 15	10, 5, 15	10.right = 15	10 / \ 5 15
4	Search 5	10, 5, 15	Traverse: 10 -> left	Found 5 at left of 10
5	Search 20	10, 5, 15	Traverse: 10 -> right -> 15 -> right None	20 not found
6	Insert 20	10, 5, 15, 20	15.right = 20	10 / \ 5 15 \ 20

💡 Search ends when node found or reached None pointer

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6
root	None	10	10	10	10	10	10
10.left	None	None	5	5	5	5	5
10.right	None	None	None	15	15	15	15
15.right	None	None	None	None	None	None	20

Key Moments - 3 Insights

Why does searching in a plain binary tree take longer than in a BST?

Because in a plain binary tree, nodes are placed without order, so search must check every node (see step 4 and 5 in execution_table). In BST, search follows left or right based on value, reducing steps.

Why do we insert nodes in BST with left < parent < right?

This ordering keeps the tree sorted, allowing efficient search by deciding direction at each node (shown in pointer changes in steps 2, 3, and 6).

What happens when searching for a value not in the BST?

Search follows the path until it reaches a None pointer (step 5), then stops and reports not found, avoiding full tree traversal unlike plain binary tree.

Visual Quiz - 3 Questions

Look at the execution_table, what is the pointer change when inserting 15?

A 10.left = 15

B 10.right = 15

C 15.left = 10

D root = 15

💡 Hint

Check step 3 in execution_table under Pointer Changes

At which step does the search for 20 end without finding the node?

A Step 4

B Step 5

C Step 6

D Step 3

💡 Hint

Look at step 5 in execution_table where search for 20 ends

If we insert 12 after step 6, where will it be placed?

A Left child of 15

B Right child of 10

C Left child of 20

D Right child of 5

💡 Hint

Recall BST rule: left < parent < right and check current tree state at step 6

Concept Snapshot

Plain Binary Tree: nodes inserted anywhere, no order
Search time: O(n) worst case
BST: nodes inserted with left < parent < right order
Search time: O(log n) average
BST enables faster search, insert, delete by ordered structure

Full Transcript

A plain binary tree inserts nodes without any order, so searching for a value requires checking many or all nodes, leading to slow search times. A Binary Search Tree (BST) inserts nodes so that left children are less than the parent and right children are greater. This order lets us decide to go left or right when searching, making search faster on average. The execution steps show inserting nodes 10, 5, 15 in BST order, then searching for 5 and 20. Searching for 5 finds it quickly by going left from 10. Searching for 20 goes right from 10 to 15, then right again but finds no node, so search ends. Inserting 20 adds it as right child of 15. This ordered structure is why BST is preferred over plain binary tree for efficient search and updates.

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