Trees6 min read

Binary Trees

A family tree where every parent has at most two children

traverse: \(O(n)\)space: \(O(h)\) where h=height

Picture a family tree — but a very strict one. Every person can have at most two children: a left child and a right child. That's a binary tree.

The person at the very top is called the root. People at the bottom with no children are called leaves. Everyone in between is an internal node.

Key vocabulary

Root — the top node, the starting point
Parent — a node that has children below it
Child — a node directly below a parent
Leaf — a node with no children
Height — the number of edges on the longest path from root to a leaf
Depth — how far a node is from the root

Why binary trees matter

Binary trees are everywhere in computer science. File explorers, compilers, databases — all use tree structures. The binary constraint (at most 2 children) makes them especially efficient to reason about and implement.

◈ Watch traversals

← → arrow keys to step · click elements to interact

Tree Traversals

class Node:
    def __init__(self, v, l=None, r=None): self.v=v; self.left=l; self.right=r

#       4
#      / \
#     2   6
#    / \ / \
#   1  3 5  7
root = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))

def inorder(n):   return inorder(n.left)   + [n.v] + inorder(n.right)   if n else []
def preorder(n):  return [n.v] + preorder(n.left)  + preorder(n.right)  if n else []
def postorder(n): return postorder(n.left) + postorder(n.right) + [n.v] if n else []

print(inorder(root))   # [1,2,3,4,5,6,7]
print(preorder(root))  # [4,2,1,3,6,5,7]
print(postorder(root)) # [1,3,2,5,7,6,4]

Output

[1, 2, 3, 4, 5, 6, 7]
[4, 2, 1, 3, 6, 5, 7]
[1, 3, 2, 5, 7, 6, 4]

Four ways to visit every node

"Traversal" means visiting every node exactly once. The order you visit them depends on which traversal you use. Think of it like reading a book — do you read the chapter title first, or the content?

Pre-order: Root → Left → Right

Visit the root before its subtrees. Like reading a book's table of contents before the chapters. Used to copy a tree or serialize its structure.

pseudocode

pre_order(node):
  visit(node)
  pre_order(node.left)
  pre_order(node.right)

In-order: Left → Root → Right

Visit the left subtree, then the root, then the right subtree. For a Binary Search Tree, in-order traversal gives you all values in sorted ascending order — a very handy property.

pseudocode

in_order(node):
  in_order(node.left)
  visit(node)
  in_order(node.right)

Post-order: Left → Right → Root

Visit children before the parent. Useful when you need to process or delete children before their parent — like calculating folder sizes (you need sub-folder sizes before the folder total).

pseudocode

post_order(node):
  post_order(node.left)
  post_order(node.right)
  visit(node)

Level-order: BFS row by row

Visit nodes level by level, left to right — like reading a paragraph normally. Uses a queue rather than recursion. Great for finding the shortest path or printing a tree visually.

pseudocode

level_order(root):
  queue = [root]
  while queue:
    node = queue.dequeue()
    visit(node)
    if node.left:  queue.enqueue(node.left)
    if node.right: queue.enqueue(node.right)

Note: Memory trick: Pre/In/Post refer to when you visit the ROOT relative to its children. Pre = root first. In = root in the middle. Post = root last.

Complexity

Pre-order traversalVisit every node once

Linear\(O(n)\)

In-order traversalVisit every node once — gives sorted output in BST

Linear\(O(n)\)

Post-order traversalVisit every node once

Linear\(O(n)\)

Level-order (BFS)Visit every node once, uses \(O(w)\) queue (w = max width)

Linear\(O(n)\)

Space (call stack)h=log n for balanced, h=n for degenerate tree

Height\(O(h)\)

Full vs. Complete vs. Perfect

These are special shapes that binary trees can have:

Full binary tree — every node has either 0 or 2 children (never 1)
Complete binary tree — all levels are fully filled except possibly the last, which is filled left to right. Heaps use this shape.
Perfect binary tree — all interior nodes have 2 children and all leaves are at the same level. A perfect tree of height h has exactly 2^(h+1) - 1 nodes.

Height and balance

The height of a tree determines how long paths are. A balanced tree keeps height close to \(\log_2(n)\), making operations fast. An unbalanced tree can degrade to height n (like a linked list), making traversals slow in terms of stack depth.

Level-Order (BFS) Traversal

from collections import deque
class Node:
    def __init__(self, v, l=None, r=None): self.v=v; self.left=l; self.right=r

root = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))

def level_order(root):
    if not root: return []
    q, levels = deque([root]), []
    while q:
        level = []
        for _ in range(len(q)):
            n = q.popleft()
            level.append(n.v)
            if n.left:  q.append(n.left)
            if n.right: q.append(n.right)
        levels.append(level)
    return levels

print(level_order(root))  # [[4],[2,6],[1,3,5,7]]

Output

[[4], [2, 6], [1, 3, 5, 7]]

Challenge

Quick check

For the tree with root 4, left subtree {2,1,3} and right subtree {6,5,7}, what does in-order traversal produce?

Binary Search Tree

A sorted binary tree — left is smaller, right is bigger

→

Trie (Prefix Tree)

Store strings by their prefixes — autocomplete in \(O(L)\) time

→

N-ary Trees

When nodes can have any number of children — file systems, DOM, org charts

→