Binary Trees Explained

A binary tree is a hierarchical data structure in which every node has at most two children, conventionally called the left child and the right child. Binary trees are the foundation for a huge slice of the DSA toolkit — binary search trees, heaps, and tries all build directly on top of the plain binary tree. Once you understand how to build one, walk it, and reason about its shape, the more specialized tree structures become variations on a familiar theme.

Overview / How it works

A binary tree is made of nodes. Each node stores a value plus two references (pointers): one to its left child and one to its right child. A reference that has no child is simply None. The topmost node is the root; a node with no children is a leaf; the connection between a node and a child is an edge; and a sequence of edges from one node to another is a path. The depth of a node is the number of edges from the root down to that node, and the height of the tree is the number of edges on the longest path from the root down to a leaf (an empty tree is usually given height -1, and a single-node tree has height 0).

Consider this small tree, which we will reuse throughout the lesson:

Here 1 is the root, 4 and 5 are leaves under 2, and 3 is also a leaf. The height of this tree is 2 (root → 2 → 4 is the longest path, two edges).

A key idea is that a binary tree is defined recursively: a binary tree is either empty, or it is a root value plus a left subtree and a right subtree, each of which is itself a binary tree. This is exactly why almost every binary tree algorithm is naturally written as a recursive function that handles the empty case (None) as its base case, then combines the results from the left and right subtrees.

Terminology you will see used

Full binary tree — every node has either 0 or 2 children (never exactly 1).
Perfect binary tree — every internal node has 2 children and every leaf sits at the same depth.
Complete binary tree — every level is completely filled except possibly the last, which is filled left to right (this is the shape a binary heap relies on).
Balanced binary tree — the height is kept at O(log n) relative to the number of nodes, usually by an explicit rebalancing rule.

Note that a plain binary tree, on its own, has no ordering rule between a node and its children — values can be arranged however you like. A binary search tree (BST) is a binary tree with an additional invariant (left subtree values are smaller, right subtree values are larger), which is covered in its own lesson. Everything in this lesson — traversals, height, search by inspection — applies to any binary tree, ordered or not.

Time and Space Complexity

Let n be the number of nodes in the tree and h be its height. Because a general binary tree has no ordering invariant, algorithms that need to find something usually cannot skip any subtree, so most operations are stated in terms of n rather than h.

Operation	Time	Space	Why
DFS traversal (preorder / inorder / postorder)	`O(n)`	`O(h)`	Every node is visited exactly once, so time is linear in the node count. Space is the maximum depth of the recursion call stack, which equals the tree’s height.
Level-order traversal (BFS)	`O(n)`	`O(w)`, up to `O(n)`	Every node is enqueued and dequeued once. The queue never holds more than the widest level `w`, which in the worst case (a complete tree’s last level) is close to `n / 2`.
Search by value (unordered)	`O(n)` worst case	`O(h)`	With no ordering to rule out a subtree, you may have to inspect every node before finding (or ruling out) the target.
Compute height / count nodes	`O(n)`	`O(h)`	Both require visiting every node once, recursively combining results from the left and right subtrees.

The gap between O(log n) and O(n) space comes entirely from shape: a balanced tree has h ≈ log₂ n, but a skewed tree (every node has only a left child, say) degenerates into a linked list with h = n - 1. This matters in Python specifically because the default recursion limit is around 1000 — a recursive traversal over a severely skewed tree of a few thousand nodes can raise RecursionError. For very deep or attacker-controlled trees, prefer an iterative traversal that manages its own explicit stack or queue (as the level-order example below already does).

Examples

Example 1: Building a tree and a preorder traversal

First, a minimal TreeNode class, then a recursive preorder traversal (visit the node itself, then the left subtree, then the right subtree):

class TreeNode:
    def __init__(self, value: int, left: "TreeNode | None" = None, right: "TreeNode | None" = None) -> None:
        self.value = value
        self.left = left
        self.right = right


def preorder(node: "TreeNode | None") -> list[int]:
    if node is None:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)


root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder(root))

Output:

[1, 2, 4, 5, 3]

The TreeNode(2, TreeNode(4), TreeNode(5)) call builds the left subtree rooted at 2 with children 4 and 5; TreeNode(3) is a leaf on the right. preorder(root) visits 1 first, then recurses fully into the left subtree (2, then 4, then 5) before moving to the right subtree (3), matching the printed list exactly.

Example 2: All three depth-first orders

The only difference between preorder, inorder, and postorder is when the current node’s value is added relative to the two recursive calls:

class TreeNode:
    def __init__(self, value: int, left: "TreeNode | None" = None, right: "TreeNode | None" = None) -> None:
        self.value = value
        self.left = left
        self.right = right


def inorder(node: "TreeNode | None") -> list[int]:
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)


def preorder(node: "TreeNode | None") -> list[int]:
    if node is None:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)


def postorder(node: "TreeNode | None") -> list[int]:
    if node is None:
        return []
    return postorder(node.left) + postorder(node.right) + [node.value]


root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print("Inorder:", inorder(root))
print("Preorder:", preorder(root))
print("Postorder:", postorder(root))

Output:

Inorder: [4, 2, 5, 1, 3]
Preorder: [1, 2, 4, 5, 3]
Postorder: [4, 5, 2, 3, 1]

inorder puts the value between the two recursive calls, so it descends all the way left first (4), backs up to its parent (2), goes right (5), then finally emits the root (1) before doing the same for the right subtree (3) — hence [4, 2, 5, 1, 3]. postorder puts the value last, so children are always emitted before their parent, and the root 1 is the very last item.

Example 3: Level-order traversal (BFS) and height

Depth-first orders dive down one branch at a time; a level-order traversal instead visits the tree row by row, using a queue (collections.deque gives O(1) appends/pops from both ends, unlike a plain list, where pop(0) is O(n)):

from collections import deque


class TreeNode:
    def __init__(self, value: int, left: "TreeNode | None" = None, right: "TreeNode | None" = None) -> None:
        self.value = value
        self.left = left
        self.right = right


def level_order(root: "TreeNode | None") -> list[list[int]]:
    if root is None:
        return []
    result: list[list[int]] = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level_values = []
        for _ in range(level_size):
            node = queue.popleft()
            level_values.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(level_values)
    return result


def height(node: "TreeNode | None") -> int:
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))


root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print("Level order:", level_order(root))
print("Height:", height(root))

Output:

Level order: [[1], [2, 3], [4, 5]]
Height: 2

level_order processes the queue one full level at a time by snapshotting len(queue) before the inner loop, so each pass appends exactly one row ([1], then [2, 3], then [4, 5]) to result. height recurses to the bottom and adds 1 back up each return, giving 2 for the root — two edges on the path 1 → 2 → 4.

How it works step by step

Tracing the level-order BFS from Example 3 on the same tree makes the queue-driven mechanics concrete:

Start: queue = [1], result = [].
level_size = 1. Dequeue 1, add it to level_values, enqueue its children 2 and 3. Queue is now [2, 3]. After the inner loop, result = [[1]].
level_size = 2. Dequeue 2, enqueue its children 4 and 5; dequeue 3, it has no children to enqueue. Queue is now [4, 5]. After the inner loop, result = [[1], [2, 3]].
level_size = 2. Dequeue 4 and 5, neither has children, so the queue becomes empty. result = [[1], [2, 3], [4, 5]].
The queue is now empty, the while queue loop ends, and level_order returns result.

The reason level order visits nodes in the order it does — entirely by row, left to right — is that the queue is FIFO: a node’s children are only ever appended after every node already waiting in the queue (i.e. the rest of the current level) has been processed.

Common Mistakes

Mistake 1: Treating any binary tree as if it were sorted

It is tempting to write a fast-looking search that compares against node.value the way you would in a binary search tree. But a plain binary tree has no such ordering guarantee — applying BST-style pruning to it silently gives wrong answers:

def find(node: "TreeNode | None", target: int) -> bool:
    if node is None:
        return False
    if node.value == target:
        return True
    elif target < node.value:
        return find(node.left, target)
    else:
        return find(node.right, target)

# Tree from the Examples section:
#        1
#       / \
#      2   3
#     / \
#    4   5
#
# find(root, 5) incorrectly returns False even though 5 IS in the tree,
# because this logic assumes a binary SEARCH tree ordering that this
# plain binary tree was never built with.

Since 5 < 1 is false, this code goes right into the 3 subtree and never even looks at the left subtree where 5 actually lives. The fix is to search both subtrees unconditionally, since there is no ordering information to rule either one out:

class TreeNode:
    def __init__(self, value: int, left: "TreeNode | None" = None, right: "TreeNode | None" = None) -> None:
        self.value = value
        self.left = left
        self.right = right


def find(node: "TreeNode | None", target: int) -> bool:
    if node is None:
        return False
    if node.value == target:
        return True
    return find(node.left, target) or find(node.right, target)


root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(find(root, 5))
print(find(root, 6))

Output:

True
False

Mistake 2: Forgetting the recursive base case

Every recursive tree function must check for None before touching .value, .left, or .right. Skip it, and the recursion eventually steps onto a missing child and crashes:

def preorder_broken(node: "TreeNode") -> list[int]:
    return [node.value] + preorder_broken(node.left) + preorder_broken(node.right)


root = TreeNode(1, TreeNode(2), None)
print(preorder_broken(root))
# Raises: AttributeError: 'NoneType' object has no attribute 'value'
# The recursion never checks for node is None, so once it steps onto
# a missing child it tries to read .value off of None.

Here root.right is None, and preorder_broken(None) immediately tries to evaluate node.value, raising AttributeError before anything is printed. Adding the base case fixes it:

class TreeNode:
    def __init__(self, value: int, left: "TreeNode | None" = None, right: "TreeNode | None" = None) -> None:
        self.value = value
        self.left = left
        self.right = right


def preorder_fixed(node: "TreeNode | None") -> list[int]:
    if node is None:
        return []
    return [node.value] + preorder_fixed(node.left) + preorder_fixed(node.right)


root = TreeNode(1, TreeNode(2), None)
print(preorder_fixed(root))

Output:

[1, 2]

This same class of bug shows up as unbounded recursion in other contexts (for example, a base case that is never reachable), so always write the None/empty check first and verify by hand that every recursive path eventually reaches it.

Best Practices

Always write the None (empty subtree) check first in a recursive tree function — it is the base case that makes the recursion terminate.
Use recursion for readability on trees you know are reasonably shallow or balanced; switch to an iterative traversal with an explicit stack (DFS) or collections.deque (BFS) when the tree could be very deep, since Python’s recursion limit is only around 1000 frames.
Reach for level-order (BFS) when you need shortest-path-style answers (minimum depth, nodes grouped by level, or the last row of a tree) — DFS orders don’t naturally expose “how many edges from the root” information.
Reach for inorder specifically when the tree is a binary search tree — it visits nodes in sorted order. For a plain (unordered) binary tree, inorder has no special meaning beyond “left subtree, then root, then right subtree.”
Don’t assume a general binary tree supports fast search, insert, or delete — those are properties of a balanced binary search tree, not of binary trees in general.
Prefer collections.deque over a plain list as a queue; list.pop(0) is O(n), which would silently turn a linear BFS into a quadratic one.

Practice Exercises

Count the nodes. Write count_nodes(root) that returns the total number of nodes in a binary tree. Hint: it’s 0 for an empty tree, otherwise 1 plus the counts of both subtrees. On the tree from the Examples section, it should return 5.
Check for symmetry. Write is_symmetric(root) that returns True if the tree is a mirror image of itself around its center (like a reflection). Hint: write a helper that compares two subtrees, checking that their roots match and that each one’s left mirrors the other’s right.
Iterative max depth. Rewrite the height function from Example 3 without recursion, using a queue (BFS) or an explicit stack (DFS) instead, so it can handle a tree too deep for the default recursion limit.

Summary

A binary tree is a set of nodes where each node has at most two children (left and right); it is defined recursively as an empty tree or a root plus two smaller binary trees.
Key terms: root, leaf, edge, depth, height, and the full/perfect/complete/balanced shape variants. A plain binary tree has no ordering guarantee — that’s what distinguishes it from a binary search tree.
Preorder (root, left, right), inorder (left, root, right), and postorder (left, right, root) are the three depth-first traversal orders; level-order (BFS, via a queue) visits row by row.
All traversals are O(n) time, since every node is visited once. DFS recursion uses O(h) space on the call stack; BFS uses O(w) space in the queue, where h is height and w is the widest level.
Search in an unordered binary tree is O(n) worst case — there’s no ordering to prune a subtree, unlike a binary search tree.
Always check for None as the recursive base case, and never assume BST-style ordering unless the tree is actually a BST.

Binary Trees Explained

Overview / How it works

Terminology you will see used

Time and Space Complexity

Examples

Example 1: Building a tree and a preorder traversal

Example 2: All three depth-first orders

Example 3: Level-order traversal (BFS) and height

How it works step by step

Common Mistakes

Mistake 1: Treating any binary tree as if it were sorted

Mistake 2: Forgetting the recursive base case

Best Practices

Practice Exercises

Summary

Table of Contents