Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA Rust - Why This Pattern

Mental Model

Trees organize data in a branching way so we can find things faster than just going one by one.

Analogy: Think of a family tree or a company chart where each person or role connects to many others below, making it easy to find someone by following branches instead of checking everyone in a line.

      [Root]
      /    \
   [L]      [R]
  /   \    /   \
[L1] [L2][R1] [R2]

Dry Run Walkthrough

Input: Compare searching for value 7 in array [1,3,5,7,9] vs linked list 1->3->5->7->9->null vs binary search tree with root 5, left child 3, right child 7

Goal: Show why trees let us find 7 faster than arrays or linked lists

Step 1: Search 7 in array by checking each element from start

[1, 3, 5, 7, 9]
Checking index 0: 1 (not 7)

Why: Arrays require checking each element until we find 7

Step 2: Continue checking array index 1: 3 (not 7)

[1, 3, 5, 7, 9]
Checking index 1: 3 (not 7)

Why: No shortcut, must check sequentially

Step 3: Check array index 2: 5 (not 7)

[1, 3, 5, 7, 9]
Checking index 2: 5 (not 7)

Why: Still no match, continue

Step 4: Check array index 3: 7 (found!)

[1, 3, 5, 7, 9]
Checking index 3: 7 (found)

Why: Found 7 after 4 checks

Step 5: Search 7 in linked list by moving node to node

1 -> 3 -> 5 -> 7 -> 9 -> null
At node 1 (not 7)

Why: Linked lists require moving node by node

Step 6: Move to node 3 (not 7)

1 -> 3 -> 5 -> 7 -> 9 -> null
At node 3 (not 7)

Why: No direct access, must traverse

Step 7: Move to node 5 (not 7)

1 -> 3 -> 5 -> 7 -> 9 -> null
At node 5 (not 7)

Why: Still searching

Step 8: Move to node 7 (found!)

1 -> 3 -> 5 -> 7 -> 9 -> null
At node 7 (found)

Why: Found 7 after 4 moves

Step 9: Search 7 in binary search tree starting at root 5

      [5]
     /   \
   [3]   [7]
At root 5 (7 > 5, go right)

Why: Trees let us decide which branch to follow

Step 10: Move to right child 7 (found!)

      [5]
     /   \
   [3]   [7]
At node 7 (found)

Why: Found 7 after 2 checks, faster than array or list

Result:

Array: found 7 after 4 checks
Linked List: found 7 after 4 moves
Tree: found 7 after 2 checks
Tree is faster because it skips half the data each step

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 }))
    }
}

fn search_array(arr: &[i32], target: i32) -> Option<usize> {
    for (i, &v) in arr.iter().enumerate() {
        if v == target {
            return Some(i); // found target
        }
    }
    None
}

struct ListNode {
    val: i32,
    next: Option<Box<ListNode>>,
}

impl ListNode {
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

fn search_linked_list(head: &Option<Box<ListNode>>, target: i32) -> bool {
    let mut current = head;
    while let Some(node) = current {
        if node.val == target {
            return true; // found target
        }
        current = &node.next; // move to next node
    }
    false
}

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; // found target
        } else if target < node.val {
            current = node.left.clone(); // go left
        } else {
            current = node.right.clone(); // go right
        }
    }
    false
}

fn main() {
    let arr = [1, 3, 5, 7, 9];
    println!("Search 7 in array: {:?}", search_array(&arr, 7));

    let mut head = Some(Box::new(ListNode::new(1)));
    head.as_mut().unwrap().next = Some(Box::new(ListNode::new(3)));
    head.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(ListNode::new(5)));
    head.as_mut().unwrap().next.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(ListNode::new(7)));
    head.as_mut().unwrap().next.as_mut().unwrap().next.as_mut().unwrap().next.as_mut().unwrap().next = Some(Box::new(ListNode::new(9)));
    println!("Search 7 in linked list: {}", search_linked_list(&head, 7));

    let root = TreeNode::new(5);
    root.borrow_mut().left = Some(TreeNode::new(3));
    root.borrow_mut().right = Some(TreeNode::new(7));
    println!("Search 7 in BST: {}", search_bst(Some(root), 7));
}

for (i, &v) in arr.iter().enumerate() { if v == target { return Some(i); } }

Check each array element until target found

while let Some(node) = current { if node.val == target { return true; } current = &node.next; }

Traverse linked list node by node to find target

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(); } else { current = node.right.clone(); } }

Traverse BST choosing left or right child based on comparison

Output

Search 7 in array: Some(3)

Search 7 in linked list: true

Search 7 in BST: true

Complexity Analysis

Time: O(n) for array and linked list because we may check every element; O(log n) for balanced tree because each step halves the search space

Space: O(1) extra space for all searches as we only keep pointers or indices

vs Alternative: Trees improve search speed over arrays and linked lists by avoiding full scans, trading some complexity in structure for faster lookups

Edge Cases

Empty array, linked list, or tree

Search returns None or false immediately

DSA Rust

for (i, &v) in arr.iter().enumerate() { if v == target { return Some(i); } }

Target not present in data structure

Search completes full traversal and returns None or false

DSA Rust

while let Some(node) = current { if node.val == target { return true; } current = &node.next; }

Single element structure with target present

Search finds target immediately

DSA Rust

if node.val == target { return true; }

When to Use This Pattern

When you need faster search than scanning every item, especially with sorted data, reach for tree structures because they let you skip large parts quickly.

Common Mistakes

Mistake: Trying to search a linked list like an array with direct indexing
Fix: Traverse node by node using next pointers instead of indexing

Mistake: Assuming arrays always have faster search without considering sorted data and binary search
Fix: Use trees or binary search on sorted arrays to improve search speed

Summary

Trees organize data in branches to speed up search compared to arrays and linked lists.

Use trees when you want faster search and your data can be arranged hierarchically.

The key insight is that trees let you skip half the data each step by choosing branches.

Practice

1. Why do trees exist as a data structure when we already have arrays and linked lists?

easy

A. Because trees allow hierarchical data representation which arrays and linked lists cannot efficiently provide

B. Because trees use less memory than arrays and linked lists

C. Because trees are easier to implement than arrays and linked lists

D. Because trees always have faster access time than arrays

Solution

1. Step 1: Understand the limitation of arrays and linked lists

   Arrays and linked lists store data linearly, which makes representing hierarchical relationships difficult and inefficient.

2. Step 2: Identify the advantage of trees

   Trees naturally represent hierarchical data with parent-child relationships, enabling efficient searching and organization of such data.

3. Final Answer:

   Trees allow hierarchical data representation which arrays and linked lists cannot efficiently provide -> Option A

4. Quick Check:

   Hierarchical data needs trees [OK]

Hint: Trees represent hierarchy; arrays and lists are linear [OK]

Common Mistakes:

• Thinking trees always use less memory
• Assuming trees are simpler to implement
• Believing trees always have faster access than arrays

2. Which of the following is the correct way to define a simple binary tree node struct in Rust?

easy

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

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

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

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

Solution

1. Step 1: Understand Rust ownership and recursive types

   Recursive types like trees need indirection (Box) and optional to allow empty children.

2. Step 2: Check each option

   struct Node { value: i32, left: Option, right: Option } uses Option for left and right, which is correct. struct Node { value: i32, left: Node, right: Node } is invalid because it causes infinite size. struct Node { value: i32, left: &Node, right: &Node } uses references without lifetimes. struct Node { value: i32, left: Box<Node>, right: Box<Node> } lacks Option, so no empty child allowed.

3. Final Answer:

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

4. Quick Check:

   Recursive structs need Option [OK]

Hint: Use Option for recursive tree nodes in Rust [OK]

Common Mistakes:

• Defining child nodes without Box causing infinite size
• Using references without lifetimes
• Not using Option for nullable children

3. What will be the output of the following Rust code that builds a simple binary tree and prints the root value?

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

fn main() {
    let root = Node {
        value: 10,
        left: Some(Box::new(Node { value: 5, left: None, right: None })),
        right: Some(Box::new(Node { value: 15, left: None, right: None })),
    };
    println!("{}", root.value);
}

medium

A. 15

B. 5

C. 10

D. Compilation error

Solution

1. Step 1: Analyze the tree construction

   The root node is created with value 10, left child 5, right child 15.

2. Step 2: Check the printed value

   The code prints root.value, which is 10.

3. Final Answer:

   10 -> Option C

4. Quick Check:

   Print root.value = 10 [OK]

Hint: Print root.value to get 10 [OK]

Common Mistakes:

• Confusing child values with root value
• Expecting print of left or right child
• Assuming compilation error due to Option usage

4. The following Rust code tries to create a binary tree node but fails to compile. What is the error?

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

fn main() {
    let root = Node {
        value: 1,
        left: Box::new(Node { value: 2, left: Box::new(Node { value: 3, left: None, right: None }), right: None }),
        right: Box::new(Node { value: 4, left: None, right: None }),
    };
}

medium

A. Cannot use None for Box<Node> fields; should use Option

B. Missing semicolon after struct definition

C. Box cannot be used inside structs

D. Cannot create nested structs in Rust

Solution

1. Step 1: Identify the field types and assigned values

   The struct fields left and right are Box<Node>, but code assigns None to some of them.

2. Step 2: Understand why None is invalid here

   None is an Option variant, but fields are Box<Node> (non-optional), so None cannot be assigned.

3. Final Answer:

   Cannot use None for Box<Node> fields; should use Option -> Option B

4. Quick Check:

   Use Option for nullable children [OK]

Hint: Use Option to allow None children [OK]

Common Mistakes:

• Thinking Box<Node> can be None
• Ignoring Option wrapper for nullable fields
• Assuming Box is not allowed in structs

5. Given that arrays and linked lists store data linearly, which of the following real-world problems is best solved using a tree data structure instead?

medium

A. Storing a list of daily temperatures in order

B. Maintaining a queue of customers waiting in line

C. Storing a sequence of characters in a string

D. Representing a company's organizational chart with managers and employees

Solution

1. Step 1: Analyze each problem type

   Options A, B, and D represent linear data best suited for arrays or linked lists.

2. Step 2: Identify hierarchical data

   Representing a company's organizational chart with managers and employees describes an organizational chart, which is hierarchical and fits tree structures.

3. Final Answer:

   Representing a company's organizational chart with managers and employees -> Option D

4. Quick Check:

   Hierarchical data needs trees [OK]

Hint: Use trees for hierarchical data like org charts [OK]

Common Mistakes:

• Choosing linear data problems for trees
• Confusing queues or sequences with trees
• Ignoring data relationships