-
Notifications
You must be signed in to change notification settings - Fork 0
007 — Binary Trees
Everything so far has been a straight line — arrays, linked lists, stacks, queues all move in one direction. A binary tree is the first structure in this wiki that branches.
Picture a family tree, but with a strict rule: every person has at most two children, and the two seats are labeled — "left child" and "right child." You can trace a path from any ancestor down to any descendant, but there's no shortcut sideways between cousins; you can only get from one branch to another by walking back up toward a shared ancestor first.
- 👪 The topmost person (no parent) is the root.
- 🌿 Anyone with no children is a leaf.
- 🧭 From any person, you can only see straight down through their own descendants — you have no idea what's happening in a sibling's branch without walking there.
That branching — "each node splits into at most two separate sub-problems" — is what makes trees a natural fit for anything recursive.
A binary tree is a set of nodes, where each node holds a value and up to two child references: left and right. There's no ordering rule yet (that's the binary search tree, next chapter) — a plain binary tree just describes the shape: root, branches, leaves.
Swift has no stdlib tree type — like linked lists, this is entirely hand-rolled, and TreeNode needs to be a class for the same reason Node did: children need to reference shared, mutable objects, and recursive value types (struct containing itself) aren't even expressible in Swift without indirection.
Trees are the backbone that other structures build on: heaps are trees with an ordering rule baked into the shape, binary search trees are trees with an ordering rule baked into left/right placement, and tries are trees where "children" are indexed by character rather than just left/right.
Reach for a binary tree when:
- Your data is naturally hierarchical (file systems, org charts, decision trees, parsed expressions).
- You're solving a problem that has an obvious recursive structure — "solve it for the left subtree, solve it for the right subtree, combine."
- You need
O(log n)operations and are willing to add an ordering rule (→ binary search tree, next chapter) or a heap property (→ heaps chapter).
Skip it when your data doesn't actually branch — forcing a hierarchy onto flat data just adds traversal overhead you don't need.
┌────┐
│ 8 │ ← root
└────┘
/ \
left / \ right
┌────┐ ┌────┐
│ 3 │ │ 10 │
└────┘ └────┘
/ \ \
┌────┐ ┌────┐ ┌────┐
│ 1 │ │ 6 │ │ 14 │ ← leaf
└────┘ └────┘ └────┘
(leaf) / \
┌────┐ ┌────┐
│ 4 │ │ 7 │ ← leaves
└────┘ └────┘
height (root to deepest leaf) = 3 edges
node 4 and node 7 are only reachable from each other by walking
UP to their shared ancestor (6) — no sideways shortcut.
No stdlib equivalent — this is the implementation.
final class TreeNode<T> {
var value: T
var left: TreeNode<T>?
var right: TreeNode<T>?
init(_ value: T, left: TreeNode<T>? = nil, right: TreeNode<T>? = nil) {
self.value = value
self.left = left
self.right = right
}
}Traversals — the standard ways to visit every node:
// Preorder: node, then left, then right — useful for copying/serializing a tree
func preorder<T>(_ node: TreeNode<T>?, _ visit: (T) -> Void) {
guard let node = node else { return }
visit(node.value)
preorder(node.left, visit)
preorder(node.right, visit)
}
// Inorder: left, then node, then right — visits a BST in sorted order
func inorder<T>(_ node: TreeNode<T>?, _ visit: (T) -> Void) {
guard let node = node else { return }
inorder(node.left, visit)
visit(node.value)
inorder(node.right, visit)
}
// Postorder: left, then right, then node — useful for deleting/freeing a tree bottom-up
func postorder<T>(_ node: TreeNode<T>?, _ visit: (T) -> Void) {
guard let node = node else { return }
postorder(node.left, visit)
postorder(node.right, visit)
visit(node.value)
}
// Level-order (BFS): visit layer by layer, using a queue — see Chapter 06
func levelOrder<T>(_ root: TreeNode<T>?) -> [[T]] {
guard let root = root else { return [] }
var result: [[T]] = []
var queue: [TreeNode<T>] = [root]
while !queue.isEmpty {
var level: [T] = []
var nextQueue: [TreeNode<T>] = []
for node in queue {
level.append(node.value)
if let left = node.left { nextQueue.append(left) }
if let right = node.right { nextQueue.append(right) }
}
result.append(level)
queue = nextQueue
}
return result
}| Operation | Big-O | Why |
|---|---|---|
| Search for a value | O(n) |
With no ordering rule, a plain binary tree gives you no hint about which branch to take — worst case you visit every node. See Big-O Notation. |
| Insert (first available spot) | O(n) |
Same problem — without an ordering rule, "first available spot" typically means a level-order search for an empty child slot. |
| Traversal (pre/in/post/level-order) | O(n) |
Every traversal, by definition, visits each node exactly once. |
| Access the height of a balanced tree | O(log n) |
Height is log₂(n) when the tree is roughly balanced — each level doubles the node count. |
| Access the height of a skewed tree | O(n) |
If every node has only one child, the "tree" degenerates into a linked list — height equals node count. |
A binary tree is a family tree where every parent has exactly two labeled seats — left and right — and the only way between two branches is back up through a shared ancestor.
Even a perfectly balanced binary tree with no ordering rule cannot be searched in O(log n). Explain why — specifically, what information is missing at each node that a binary search tree adds, and how that missing information is exactly what lets you discard half the remaining nodes at every step during a search.
⬅️ Previous: Queues and Deques · Next: Binary Search Trees ➡️