Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA Go - 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 job leads to many others, making it easy to find someone by following branches instead of checking everyone in a line.

Array: [1][2][3][4][5]
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> null
Tree:
      3
     / \
    1   5
       / \
      4   6

Dry Run Walkthrough

Input: Array: [1, 2, 3, 4, 5], Linked List: 1->2->3->4->5, Tree: root=3 with children 1 and 5, 5 has children 4 and 6

Goal: Show how finding a value (like 6) is faster in a tree than in an array or linked list

Step 1: Search for 6 in array by checking each element one by one

[1][2][3][4][5] (checking 1) -> not found

Why: Array requires checking each item until we find 6 or reach the end

Step 2: Continue checking array elements 2, 3, 4, 5

[1][2][3][4][5] (checking 2,3,4,5) -> not found yet

Why: No shortcuts, must check all elements in order

Step 3: 6 not found in array, search fails after full scan

[1][2][3][4][5] (end reached) -> 6 not found

Why: Array search is slow for large data because of linear scan

Step 4: Search for 6 in linked list starting at head 1

1 -> 2 -> 3 -> 4 -> 5 -> null (at 1) -> not found

Why: Linked list also requires checking each node one by one

Step 5: Move through linked list nodes 2, 3, 4, 5

1 -> 2 -> 3 -> 4 -> 5 -> null (at 5) -> not found yet

Why: No direct access, must follow pointers sequentially

Step 6: 6 not found in linked list, search fails after full traversal

1 -> 2 -> 3 -> 4 -> 5 -> null (end reached) -> 6 not found

Why: Linked list search is also slow for large data

Step 7: Search for 6 in tree starting at root 3

      3 ↑
     / \
    1   5
       / \
      4   6

Why: Tree lets us choose which branch to follow based on value

Step 8: From 3, move to right child 5 because 6 > 3

      3
     / \
    1   5 ↑
       / \
      4   6

Why: We skip left branch because 6 is greater than 3

Step 9: From 5, move to right child 6 because 6 > 5

      3
     / \
    1   5
       / \
      4   6 ↑

Why: We directly reach 6 without checking other nodes

Step 10: Found 6 in tree quickly by following branches

      3
     / \
    1   5
       / \
      4   6 ↑ (found)

Why: Tree search is faster because it narrows down choices at each step

Result:

Array: [1][2][3][4][5] (full scan)
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> null (full traversal)
Tree:
      3
     / \
    1   5
       / \
      4   6 ↑ (found)
Answer: Tree finds 6 faster by skipping unnecessary checks

Annotated Code

DSA Go

package main

import "fmt"

// Node represents a tree node
type Node struct {
	value int
	left  *Node
	right *Node
}

// SearchTree searches for target in the binary search tree
func SearchTree(root *Node, target int) bool {
	if root == nil {
		return false // base case: empty tree
	}
	if root.value == target {
		return true // found target
	}
	if target < root.value {
		return SearchTree(root.left, target) // search left subtree
	} else {
		return SearchTree(root.right, target) // search right subtree
	}
}

func main() {
	// Build tree:
	//       3
	//      / \
	//     1   5
	//        / \
	//       4   6
	root := &Node{value: 3}
	root.left = &Node{value: 1}
	root.right = &Node{value: 5}
	root.right.left = &Node{value: 4}
	root.right.right = &Node{value: 6}

	// Search for 6
	found := SearchTree(root, 6)
	fmt.Printf("Found 6 in tree: %v\n", found)

	// Simulate array search
	arr := []int{1, 2, 3, 4, 5}
	foundArr := false
	for _, v := range arr {
		if v == 6 {
			foundArr = true
			break
		}
	}
	fmt.Printf("Found 6 in array: %v\n", foundArr)

	// Simulate linked list search
	type ListNode struct {
		val  int
		next *ListNode
	}

	head := &ListNode{val: 1}
	head.next = &ListNode{val: 2}
	head.next.next = &ListNode{val: 3}
	head.next.next.next = &ListNode{val: 4}
	head.next.next.next.next = &ListNode{val: 5}

	curr := head
	foundList := false
	for curr != nil {
		if curr.val == 6 {
			foundList = true
			break
		}
		curr = curr.next
	}
	fmt.Printf("Found 6 in linked list: %v\n", foundList)
}

if root == nil { return false // base case: empty tree }

stop search if tree node is empty

if root.value == target { return true // found target }

check if current node matches target

if target < root.value { return SearchTree(root.left, target) // search left subtree } else { return SearchTree(root.right, target) // search right subtree }

choose left or right branch based on target value

for _, v := range arr { if v == 6 { foundArr = true break } }

linear scan through array to find target

for curr != nil { if curr.val == 6 { foundList = true break } curr = curr.next }

linear traversal through linked list nodes

Output

Found 6 in tree: true

Found 6 in array: false

Found 6 in linked list: false

Complexity Analysis

Time: O(n) for array and linked list because each element or node must be checked one by one; O(log n) average for balanced tree because each step halves the search space

Space: O(n) for all because data is stored in n elements or nodes; recursion stack for tree search is O(log n) on average

vs Alternative: Trees improve search speed over arrays and linked lists by organizing data hierarchically, reducing the number of checks needed

Edge Cases

Empty tree

Search returns false immediately

DSA Go

if root == nil {
	return false // base case: empty tree
}

Target not in tree

Search explores branches until leaf nodes, then returns false

DSA Go

if root == nil {
	return false // base case: empty tree
}

Single node tree with target

Search finds target immediately at root

DSA Go

if root.value == target {
	return true // found target
}

When to Use This Pattern

When you need faster search than linear scan and your data can be organized hierarchically, reach for tree structures because they let you skip large parts of data quickly.

Common Mistakes

Mistake: Trying to search a tree like an array or linked list by checking every node without using the tree's branching logic
Fix: Use the tree property to decide which branch to follow instead of checking all nodes

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 split into smaller parts at each step.

The key is that trees let you skip large parts of data by choosing branches, unlike linear structures.