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 without checking everyone.

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5, array: [1, 2, 3, 4, 5], goal: find value 5

Goal: Show how finding a value in a list or array is slower than in a tree structure

Step 1: search value 5 in linked list by checking nodes one by one

1 -> 2 -> 3 -> 4 -> [5] -> null

Why: Linked list requires checking each node until we find 5

Step 2: search value 5 in array by checking elements one by one

[1, 2, 3, 4, 5]

Why: Array also requires checking each element until 5 is found

Step 3: search value 5 in tree by choosing branches

Why: Tree lets us skip many nodes by following branches, finding 5 faster

Result:

Tree structure: 1 -> 2 -> 5 found faster than linear search in list or array

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

// Node for linked list
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};

// Node for tree
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

// Search in linked list
bool searchList(ListNode* head, int target) {
    while (head != nullptr) {
        if (head->val == target) return true; // found target
        head = head->next; // move to next node
    }
    return false; // not found
}

// Search in array
bool searchArray(const vector<int>& arr, int target) {
    for (int val : arr) {
        if (val == target) return true; // found target
    }
    return false; // not found
}

// Search in binary tree
bool searchTree(TreeNode* root, int target) {
    if (root == nullptr) return false; // base case: empty node
    if (root->val == target) return true; // found target
    // search left subtree
    if (searchTree(root->left, target)) return true;
    // search right subtree
    return searchTree(root->right, target);
}

int main() {
    // Create linked list 1->2->3->4->5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    // Create array [1,2,3,4,5]
    vector<int> arr = {1, 2, 3, 4, 5};

    // Create tree:
    //     1
    //    / \
    //   2   3
    //  / \
    // 4   5
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    int target = 5;

    cout << "Search in linked list: " << (searchList(head, target) ? "Found" : "Not Found") << endl;
    cout << "Search in array: " << (searchArray(arr, target) ? "Found" : "Not Found") << endl;
    cout << "Search in tree: " << (searchTree(root, target) ? "Found" : "Not Found") << endl;

    return 0;
}

while (head != nullptr) {

traverse linked list nodes one by one

if (head->val == target) return true;

check if current node has target value

for (int val : arr) {

iterate array elements one by one

if (val == target) return true;

check if current array element matches target

if (root == nullptr) return false;

base case: empty tree node means target not found here

if (root->val == target) return true;

check if current tree node has target value

if (searchTree(root->left, target)) return true;

search left subtree recursively

return searchTree(root->right, target);

search right subtree recursively if not found left

OutputSuccess

Search in linked list: Found Search in array: Found Search in tree: Found

Complexity Analysis

Time: O(n) because in worst case we check every element or node once

Space: O(h) for tree search due to recursion stack where h is tree height; O(1) for list and array

vs Alternative: Trees can reduce search time if balanced (O(log n)) unlike linear list or array search which is O(n)

Edge Cases

empty linked list

search returns false immediately

DSA C++

while (head != nullptr) {

empty array

search returns false immediately

DSA C++

for (int val : arr) {

empty tree

search returns false immediately

DSA C++

if (root == nullptr) return false;

When to Use This Pattern

When you need faster search or hierarchical data, think of trees because lists and arrays check items one by one.

Common Mistakes

Mistake: Trying to find a value in a tree without recursion or proper traversal
Fix: Use recursion or a queue/stack to visit nodes systematically

Summary

Trees organize data in branches to speed up search compared to linear lists or arrays.

Use trees when data has hierarchy or when faster search than linear scan is needed.

The key insight is that trees let you skip many elements by following branches, unlike lists or arrays.