Why BST Over Plain Binary Tree in DSA Rust - Why This Pattern

Mental Model

A Binary Search Tree (BST) keeps data in order so we can find things fast, unlike a plain binary tree which has no order.

Analogy: Imagine a library where books are randomly placed on shelves (plain binary tree) versus a library where books are sorted by title (BST). Finding a book in the sorted library is much quicker.

Plain Binary Tree:
    7
   / \
  3   9
 /   / \
1   8  10

BST:
    7
   / \
  3   9
 /   / \
1   8  10

Dry Run Walkthrough

Input: Plain binary tree with nodes 7, 3, 9, 1, 8, 10; search for 8

Goal: Show how searching for 8 is slower in plain binary tree and faster in BST

Step 1: Start search at root node 7 in plain binary tree

7 [searching] -> 3 -> 9 -> 1 -> 8 -> 10

Why: We begin at the root to find the value

Step 2: Check left child 3, not 8, then right child 9

7 -> 3 [searching] -> 9 -> 1 -> 8 -> 10

Why: No order, so we must check multiple branches

Step 3: Check left child 1, no match; then right child 8 found

7 -> 3 -> 9 -> 1 -> 8 [found] -> 10

Why: We must explore many nodes to find 8

Step 4: Start search at root node 7 in BST

7 [searching] -> 3 -> 9 -> 1 -> 8 -> 10

Why: Start at root for ordered search

Step 5: Since 8 > 7, move to right child 9

7 -> 9 [searching] -> 3 -> 1 -> 8 -> 10

Why: BST property guides search direction

Step 6: Since 8 < 9, move to left child 8 and find it

7 -> 9 -> 8 [found] -> 3 -> 1 -> 10

Why: BST order lets us skip unnecessary nodes

Result:

Plain binary tree search path: 7 -> 3 -> 9 -> 1 -> 8 found
BST search path: 7 -> 9 -> 8 found
BST finds 8 faster by skipping nodes

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

// Plain binary tree search: no order, search both sides
fn search_plain(root: Option<Rc<RefCell<TreeNode>>>, target: i32) -> bool {
    if root.is_none() {
        return false;
    }
    let node = root.unwrap();
    if node.borrow().val == target {
        return true;
    }
    // search left and right both
    search_plain(node.borrow().left.clone(), target) || search_plain(node.borrow().right.clone(), target)
}

// BST search: use order to decide direction
fn search_bst(root: Option<Rc<RefCell<TreeNode>>>, target: i32) -> bool {
    let mut current = root;
    while let Some(node_rc) = current {
        let node = node_rc.borrow();
        if node.val == target {
            return true;
        } else if target < node.val {
            current = node.left.clone(); // go left
        } else {
            current = node.right.clone(); // go right
        }
    }
    false
}

fn main() {
    // Build plain binary tree
    let root_plain = TreeNode::new(7);
    let node3 = TreeNode::new(3);
    let node9 = TreeNode::new(9);
    let node1 = TreeNode::new(1);
    let node8 = TreeNode::new(8);
    let node10 = TreeNode::new(10);

    root_plain.borrow_mut().left = Some(node3.clone());
    root_plain.borrow_mut().right = Some(node9.clone());
    node3.borrow_mut().left = Some(node1.clone());
    node9.borrow_mut().left = Some(node8.clone());
    node9.borrow_mut().right = Some(node10.clone());

    // Build BST with same values
    let root_bst = TreeNode::new(7);
    let node3_bst = TreeNode::new(3);
    let node9_bst = TreeNode::new(9);
    let node1_bst = TreeNode::new(1);
    let node8_bst = TreeNode::new(8);
    let node10_bst = TreeNode::new(10);

    root_bst.borrow_mut().left = Some(node3_bst.clone());
    root_bst.borrow_mut().right = Some(node9_bst.clone());
    node3_bst.borrow_mut().left = Some(node1_bst.clone());
    node9_bst.borrow_mut().left = Some(node8_bst.clone());
    node9_bst.borrow_mut().right = Some(node10_bst.clone());

    // Search for 8 in plain binary tree
    let found_plain = search_plain(Some(root_plain), 8);
    println!("Found 8 in plain binary tree: {}", found_plain);

    // Search for 8 in BST
    let found_bst = search_bst(Some(root_bst), 8);
    println!("Found 8 in BST: {}", found_bst);
}

if node.borrow().val == target { return true; }

Check if current node matches target

search_plain(node.borrow().left.clone(), target) || search_plain(node.borrow().right.clone(), target)

Search both left and right subtrees in plain tree

while let Some(node_rc) = current {

Traverse nodes while current is not None

if node.val == target { return true; } else if target < node.val { current = node.left.clone(); } else { current = node.right.clone(); }

Use BST property to decide direction to search

Output

Found 8 in plain binary tree: true

Found 8 in BST: true

Complexity Analysis

Time: O(n) for plain binary tree because we may check every node; O(h) for BST where h is tree height because we skip half branches each step

Space: O(h) for recursion stack in plain tree search; O(1) iterative space for BST search

vs Alternative: BST search is faster than plain tree search because it uses order to avoid checking all nodes

Edge Cases

Empty tree

Search returns false immediately

DSA Rust

if root.is_none() { return false; }

Target not in tree

Search explores nodes until no more to check, then returns false

DSA Rust

while let Some(node_rc) = current { ... }

Single node tree with target

Search finds target at root quickly

DSA Rust

if node.borrow().val == target { return true; }

When to Use This Pattern

When a problem involves searching or inserting in a tree and you want faster lookups, reach for BST because it keeps data ordered to speed up operations.

Common Mistakes

Mistake: Searching a plain binary tree using BST logic (going only left or right)
Fix: Use full traversal (both left and right) for plain binary tree search

Mistake: Assuming BST is always balanced
Fix: Remember BST can be skewed; balance affects performance

Summary

BST keeps data ordered to speed up search compared to plain binary tree.

Use BST when you need faster search, insert, or delete operations in a tree.

The key insight is BST's order lets you skip half the tree at each step, making search faster.

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