Binary Trees vs Arrays and Linked Lists
Different data structures organize data in different ways. Each one has strengths and weaknesses depending on whether you care more about fast access, fast insertion, or maintaining order.
1. Arrays
An array stores elements next to each other in memory.
Index: 0 1 2 3 4
Array: [10, 20, 30, 40, 50]
Strengths
- Very fast direct access to elements
arr = [10, 20, 30, 40, 50]
print(arr[3]) # O(1) → 40
Weaknesses
- Insertions and deletions are slow because elements must shift in memory
arr.insert(1, 15)
# [10, 15, 20, 30, 40, 50]
Time Complexity
| Operation | Time |
|---|---|
| Access | O(1) |
| Insert / Delete (middle) | O(n) |
2. Linked Lists
A linked list is made of nodes, where each node points to the next.
10 → 20 → 30 → 40 → None
Strengths
- Fast insertion and deletion (no shifting)
Weaknesses
- Slow access since the list must be traversed
current = head
for _ in range(3):
current = current.next
Time Complexity
| Operation | Time |
|---|---|
| Access | O(n) |
| Insert / Delete | O(1) (if node is known) |
3. Binary Trees
A binary tree organizes data hierarchically. Each node has at most two children: left and right.
30
/ \
20 40
/ \
10 25
Why Binary Trees Are Powerful
- Faster access than linked lists
- Faster insertion and deletion than arrays
- No memory shifting required
- Structured searching
Binary Search Trees (BST)
A Binary Search Tree follows this rule:
Left subtree < Node < Right subtree
30
/ \
20 40
/ \
10 25
Python Node Structure
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
Insert into a BST
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
Searching in a BST
def search(root, target):
if root is None:
return False
if root.value == target:
return True
elif target < root.value:
return search(root.left, target)
else:
return search(root.right, target)
Searching skips half of the tree at each step, giving an average time of O(log n) when the tree is balanced.
Final Comparison
| Structure | Access | Insert | Delete | Sorted | Memory Shift |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | No | Yes |
| Linked List | O(n) | O(1) | O(1) | No | No |
| Binary Tree (BST / AVL) | O(log n) | O(log n) | O(log n) | Yes | No |
Summary
- Arrays: Fast lookup, slow edits
- Linked Lists: Easy edits, slow lookup
- Binary Trees: Balanced performance