What Is a Binary Tree?
A binary tree is a hierarchical collection of nodes where every node has at most two children — a left child and a right child. Unlike arrays or linked lists, which are flat sequences, a tree branches: one node points to two, those two point to two more, and the structure fans out.
The topmost node is the root. A node with no children is a leaf. Lines connecting parents to children are edges.
A binary tree with N nodes always has exactly N − 1 edges. Every node except the root has exactly one parent.
The Vocabulary
You'll see the same handful of terms over and over. Get them in your head now and the rest of the tree material reads cleanly.
| Term | Definition | Visual |
|---|---|---|
| Root | The single top node — the only node with no parent. | Node 1 above |
| Leaf | A node with no children. | Nodes 4, 5, 3 |
| Internal node | A node with at least one child. | Nodes 1, 2 |
| Depth | Number of edges from the root to a node. Root has depth 0. | Node 4 has depth 2 |
| Height | Number of edges on the longest path from a node down to a leaf. | Tree height = 2 |
| Subtree | Any node together with all its descendants — itself a valid tree. | Node 2 and its children form a subtree |
A useful trick: height is measured looking down, depth is measured looking up.
Building a Tree in Code
A binary tree is just a node that knows about its two children. Here's the canonical Python class — you'll see this exact shape in every tree problem.
Now let's build the tree from the diagram above — value 1 at the root, 2 and 3 as its children, 4 and 5 hanging off 2:
That's it. No arrays, no parent pointers — just nodes holding references to their children. The tree exists implicitly in those .left and .right links.
Recursion — The Tree's Best Friend
Look at the TreeNode class again. A node's .left is itself a TreeNode (or None). A node's .right is itself a TreeNode (or None). The structure is defined in terms of itself — and that's exactly the shape that recursion was made for.
Almost every tree algorithm follows the same template: do something with this node, then recurse into its left and right children, with a base case for None.
The smallest non-trivial example: counting how many nodes are in the tree.
Three lines. The whole algorithm. Let's watch it run on a tiny 3-node tree — root 1 with children 2 and 3.
The call stack acts as a free traversal engine — it remembers where to come back to after each recursive dive. Once you internalise this rhythm (check None, do work, recurse left, recurse right) you can write count, sum, max-depth, mirror, equality-check, and dozens of other tree functions in three or four lines each.
What Comes Next
You now know what a binary tree is, what the vocabulary means, and how to write a recursive function over one. The next question is how to systematically visit every node — because almost every problem boils down to that.
There are two answers:
- DFS (Depth-First Search) — dive as deep as possible down one branch before backtracking. Three sub-flavours (pre-order, in-order, post-order) depending on when you do work relative to the recursive calls. Covered in the next article.
- BFS (Breadth-First Search) — sweep across the tree level by level using a queue. Covered in the article after that.
Read those two and you'll have the entire toolkit for everything that follows: BSTs, balanced trees, lowest common ancestor, path sums, serialisation. All built on these two traversal strategies.