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 that leads to exactly one next clue. A stack and a queue are both a line with rules about which end you touch. A tree is the first structure that branches. A node does not point to one next thing. It can point to two.
Think of a family tree, or a company org chart. One person is at the top with no boss above them. Each person can have up to two people that report directly below them. From any one person, you can see only their own two direct reports, not the whole chart at the same time. To reach someone three levels down, you must go through the people between you and them, one hop at a time.
A binary tree is this exact shape, made formal. Each node holds a value and two pointers, left and right. Each pointer points to another node or to nothing. The one node that 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 a branch, with nobody that reports to them.
The node
structure Node:
value
left // -> another Node, or NULL
right // -> another Node, or NULL
// The tree itself is a reference to its root node. A NULL root is an empty tree.preorder 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 one time, so time is O(n) for all of them: preorder, inorder, postorder, level-order, and height are all O(n). Space is where they are different. The three DFS traversals recurse, so their space cost is the depth of the call stack: O(h), where h is the height of the tree. Remember Recursion Basics: a pending call stays in memory until it returns. BFS never recurses, but its queue can hold a full level at the same time.
| Operation | Time | Space | Why |
|---|---|---|---|
| Preorder / inorder / postorder (DFS) | O(n) | O(h) | Every node is visited one time, which is O(n) time. The recursion stack holds one frame per level of depth that is being explored now. So its size is the height h of the tree: O(log n) if the tree is balanced, and O(n) in the worst case if it is a fully skewed chain. |
| Level-order (BFS) | O(n) | O(n) | Every node is enqueued and dequeued one time, which is O(n) time. But the queue can hold a full level at the same time, and the widest level of a balanced tree can hold up to about n/2 nodes. So the queue space is O(n) in the worst case, not O(h). |
| height(node) | O(n) | O(h) | This is the same shape as any DFS traversal. It visits every node one time, and the recursion never goes deeper than the height of the tree. |
Empty tree
Every function above starts with the same check. preorder, inorder, and postorder on a NULL node return without an append. levelOrder returns an empty list before it touches a queue. height(NULL) returns 0. If you skip this check anywhere, 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 one time 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 one with no children, adds one level on top of that.
Skewed tree — every node has only one child
Nothing stops a binary tree from becoming the exact shape of a linked list: one long chain, n nodes deep, with no 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. 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. If you write the recursive calls in the wrong order (for example, right before left), you get a valid-looking but wrong sequence with no error. It is easy to miss on a tree bigger than three nodes.
Sign in to mark problems done — progress syncs across devices.