Binary Trees
Quick reference
| Preorder / inorder / postorder (DFS) | O(n) |
| Level-order (BFS) | O(n) |
| height(node) | O(n) |
Every structure so far has been a straight line. An array is a row of lockers. A linked list is a scavenger hunt, one clue leading to exactly one next clue. A stack and a queue are both just a line with rules about which end you touch. A tree is the first structure that branches: a node doesn't point to one next thing, it can point to two.
Think of a family tree, or a company org chart. One person sits at the top with no boss above them. Each person can have up to two people reporting directly below them. From any one person, you can only see their own two direct reports — not the whole chart at once — and to reach someone three levels down you have to go through whoever sits between you and them, one hop at a time.
A binary tree is exactly that shape, formalized. Each node holds a value and two pointers, left and right, each either pointing to another node or to nothing. The one node nobody points to is the root — the top of the chart. A node whose left and right are both empty is a leaf — the bottom of some branch, nobody reporting to them.
The node
structure Node:
value
left // -> another Node, or NULL
right // -> another Node, or NULL
// the tree itself is just a reference to its root node — a NULL root is an empty treepreorder traversal — root, left, right
function preorder(node, result):
if node is NULL: // base case — nothing here to visit
return
result.append(node.value) // visit the root before either subtree
preorder(node.left, result)
preorder(node.right, result)inorder traversal — left, root, right
function inorder(node, result):
if node is NULL:
return
inorder(node.left, result)
result.append(node.value) // visit the root between the two subtrees
inorder(node.right, result)postorder traversal — left, right, root
function postorder(node, result):
if node is NULL:
return
postorder(node.left, result)
postorder(node.right, result)
result.append(node.value) // visit the root last, after both subtrees are donelevel-order traversal (BFS) — one level at a time, using a queue
function levelOrder(root):
result = []
if root is NULL:
return result
queue = Queue()
enqueue(queue, root)
while queue is not empty:
node = dequeue(queue)
result.append(node.value)
if node.left is not NULL:
enqueue(queue, node.left)
if node.right is not NULL:
enqueue(queue, node.right)
return resultheight — 1 + the taller of the two subtrees
function height(node):
if node is NULL: // base case — an empty subtree has height 0
return 0
return 1 + max(height(node.left), height(node.right))Every traversal touches each node exactly once, so time is O(n) across the board — preorder, inorder, postorder, level-order, height, all O(n). Space is where they split. The three DFS traversals recurse, so their space cost is the call stack depth: O(h), where h is the tree's height — recall Recursion Basics, a pending call sits in memory until it returns. BFS never recurses, but its queue can hold an entire level at once.
| Operation | Time | Space | Why |
|---|---|---|---|
| Preorder / inorder / postorder (DFS) | O(n) | O(h) | Every node is visited once — O(n) time. The recursion stack holds one frame per level of depth currently being explored, so its size is the tree's height h: O(log n) if the tree is balanced, O(n) worst case if it's a totally skewed chain. |
| Level-order (BFS) | O(n) | O(n) | Every node is enqueued and dequeued once — O(n) time. But the queue can hold an entire level at once, and the widest level of a balanced tree can hold up to roughly n/2 nodes — so queue space is O(n) worst case, not O(h). |
| height(node) | O(n) | O(h) | Same shape as any DFS traversal: visits every node once, and the recursion never goes deeper than the tree's own height. |
Empty tree
Every function above starts with the same check. preorder/inorder/postorder on a NULL node just return without appending anything; levelOrder returns an empty list before ever touching a queue; height(NULL) returns 0. Skip this check anywhere and you dereference a node that was never there.
Single node
The root is a leaf at the same time — both descriptions are true of the exact same node. All three DFS orders visit it once and stop; levelOrder enqueues it, dequeues it, finds no children to enqueue, and the queue is empty on the next check. height returns 1, not 0 — the base case (NULL) is 0, but a real node, even a childless one, adds one level on top of that.
Skewed tree — every node has only one child
Nothing stops a binary tree from degenerating into the exact shape of a linked list — one long chain, n nodes deep, zero branching. height(node) then returns n instead of log₂(n): the O(h) space bound from Know It becomes O(n) in the worst case, not O(log n). This matters more than it looks like it should — the next topic builds a structure directly on top of binary trees where this exact shape is the main failure mode to watch for.
Mixing up the three DFS orders
Take the 3-node tree with root 2, left child 1, right child 3. Preorder (root, left, right) reads 2, 1, 3. Inorder (left, root, right) reads 1, 2, 3. Postorder (left, right, root) reads 1, 3, 2. All three visit the same three nodes; only the position of the root relative to the two subtrees changes — first, middle, or last. Writing the recursive calls in the wrong order (say, right before left) silently produces a valid-looking but wrong sequence, and it's easy to not notice on a tree bigger than three nodes.
Sign in to mark problems done — progress syncs across devices.