The Binary Tree
A linked list node holds one reference to the next node. Let a node hold two, and the chain becomes a tree. A tree is the natural shape for layered data, and it is where recursion first earns its place. Learn one sentence — a tree is a root plus a left subtree and a right subtree — and the next five chapters are variations on it.
Intuition: a lot of information is layered
Family trees, folders, org charts — a straight line cannot express a hierarchy.
Every structure so far has been a straight line: array, linked list, stack, queue. Each element has at most one “next”. But look at the information around you. Folders contain folders. One manager sits above several directors. One ancestor has many descendants. This page itself (the HTML DOM) is tags inside tags. A hierarchy is everywhere, and a straight line cannot hold one.
How do you upgrade? Recall the linked list: each node has one next reference pointing at the following node. Now allow a node to point at more than one next node. The chain immediately grows into a tree drawn upside down: the root is at the top, branches spread downward, and the ends are leaves. If every node points at no more than two, called left and right, the structure is a binary tree. Why exactly two? Two branches already express any yes-or-no decision, which is what the binary search tree in the next chapter is built on. And a tree with any number of children can be rewritten in binary form, by letting left mean “first child” and right mean “next sibling”. So the binary tree is the standard building block of the whole family.
Every node has at most one left child and at most one right child, and the two positions are not interchangeable: a node with only a left child is a different tree from a node with only a right child. A child may be missing; there can never be a third.
Every node except the root has exactly one parent, and following child references never leads back to an ancestor. Drop this rule and the structure becomes a graph, which is chapter 12.
Look down from any node and you see a valid binary tree again: its subtree. This self-similarity is the reason recursion works here, and the chapter uses it on every page.
First the vocabulary. Every problem statement later in this chapter is written with these words.
Two of those words carry a number, and this course counts that number in edges — the usual convention. The depth of a node is the number of edges from the root down to it, so the root has depth 0. The height of a node is the number of edges on the longest path from it down to a leaf, so a leaf has height 0. The height of the tree is the height of its root. A tree holding only a root therefore has height 0, and an empty tree is conventionally −1. Chapters 8 and 9 keep this definition, so their formulas can be compared directly.
Three shapes have names of their own. Read the naming carefully: the Chinese and the English terms do not line up the way you would guess, and the third one is what chapter 09 builds the heap on.
Every node has either two children or none. Node 2 is a leaf, node 3 has both children, so this tree is full. Gaps in the middle of a level are allowed, which is why it is not complete: slots [3] and [4] are empty while [5] and [6] are used.
Every level is completely filled, so all leaves sit at the same depth. A perfect tree of height h has 2h+1−1 nodes; here h = 2 and the tree has 7. Note the Chinese name: 满二叉树 means perfect, not “full”.
Every level is filled except possibly the last, and the last is filled from left to right. The used indices then form one unbroken run [0]…[5], so the tree fits into an array with no wasted slot. Chapter 09 builds the heap on exactly this property.
Why a complete tree fits into an array
Number the nodes in level order, starting at 0. Then the children of node i sit at 2i+1 and 2i+2, and its parent sits at (i-1)/2 rounded down. The arithmetic replaces the references completely. It only pays off when the used numbers form one unbroken run, which is exactly the definition of a complete tree: n nodes need an array of n slots. For other shapes the run has holes. A chain of n nodes that always leans right puts its deepest node at index 2n−2, so the array would need 2n−1 slots to hold n values. That is why array storage is reserved for complete trees, and why the heap in chapter 09 keeps itself complete on purpose.
Where you already meet trees
A browser renders a page by walking the DOM tree. ls -R walks a directory tree. A compiler turns your source into a syntax tree (AST) before translating it. Parsed JSON is a tree. A database index is usually a B+ tree, which is not binary but follows the same idea: a hierarchy with a bounded number of children per node. Wherever data nests, a tree is its shape, and that is why tree traversal shows up in so many interviews.
In memory: one value, two references
TreeNode = val + left + right. Still references, still addresses.
A tree node is a close relative of a linked list node. The ListNode of chapter 3 holds a val and one next reference, and a reference is the address of another object, not the object itself (see the introduction, §03). TreeNode keeps the same idea and holds two references instead of one:
[ val | next → ]
Only one direction is available, so the structure can only be a line. The nodes themselves are scattered anywhere in the heap and are held together by next.
[ ← left | val | right → ]
Every step is a choice between left and right. The nodes are still scattered in the heap. The tree shape exists only in what the references point at; there is no drawn tree anywhere in memory.
The one sentence this chapter is built on
A binary tree is either empty, or it is one root node plus a left subtree and a right subtree — and each of those two subtrees is itself a binary tree. Notice that the empty tree counts as a tree. It is not an exception to be tolerated; it is the floor the recursion stands on. Both children of a leaf are empty trees, so “what do I do with an empty tree” is always the first line of the code. Read that sentence three times. Everything else in this chapter is a translation of it.
A useful count: a tree with n nodes has 2n child slots. Only n−1 of them are used, because every node except the root is the child of exactly one node. The other n+1 slots hold null. There are more nulls than nodes. That is why the base case is reached so often, and why leaving it out is not untidy but fatal.
Recursion: a function that calls itself
★ Start hereThe shape of a tree is recursive, so the code that handles it is recursive too. This is where recursion is taught.
Warm up away from trees, with the smallest possible example. The definition of factorial: n! = n × (n−1)!, and 0! = 1! = 1. Notice that the definition uses factorial to explain factorial. In mathematics that is called a recursive definition. In code it is a function that calls itself:
“The function has not finished, and it calls itself. Does the computer not get confused?” It does not, because of the call stack (the CallStack from chapter 4 again). Each call pushes a new frame, and each frame keeps its own arguments and its own position in the code. Watch factorial(3) from beginning to end:
Writing a recursion means answering three questions. Nothing else.
One sentence that says exactly what the function gives back, and it must be true for every node, not only the root. For counting nodes: count(node) returns how many nodes are in the subtree rooted at node. Without this sentence the other two questions cannot be answered.
The smallest input you can answer without recursing. For factorial it is n ≤ 1. On a tree it is almost always the empty tree, node == null. It goes on the first line, and the value it returns has to satisfy the promise from question 1: count(null) = 0.
Assume the recursive calls have already returned correct answers, then build this node answer from them: count(node) = 1 + count(left) + count(right). The assumption is allowed because it is the induction hypothesis, not optimism — see the note at the end of this section. This is the only step you actually design.
Now back to the tree. §02 says a tree is a root plus a left subtree plus a right subtree, so counting the nodes is already recursive in shape. Answer the three questions: the promise is count(node) returns the number of nodes in the subtree rooted at node; the base case is count(null) = 0; the combination is 1 + count(left) + count(right). Watch it run on a tree of 7 nodes. The stack on the right rises and falls, and each node shows the value it returns the moment it finishes:
The most common mistake: no base case
Without if (node == null) return 0; the code will try to read null.left and throw a null pointer error. In other shapes of the same mistake the function calls itself forever, the frames pile up to tens of thousands, and Java and JavaScript raise a stack overflow while Python raises RecursionError. Build the habit: the first line always asks what to do with an empty tree. §05 lists the recursion depth limit of each language.
Why assuming the answer is not wishful thinking
Mathematical induction: prove the statement for n = 1 (the base case), then prove that if it holds for n−1 it holds for n (the combination step), and it holds for every n. Recursion is the executable version of the same argument. Two conditions make it valid: the base case must be correct, and every call must be strictly smaller, so the base case is always reached. A beginner tries to unfold three levels in their head and loses track. The working method is to check one level only: given correct answers from the children, is my answer correct?
Four traversals: flattening a tree into a sequence
★ Core of the chapterPreorder, inorder, and postorder are one route with three visiting times. Level order is a different walk, driven by a queue.
A tree is two-dimensional, but printing, comparing, and serializing all need a one-dimensional sequence. Visiting every node in a fixed order is called a traversal. Depth-first search (DFS) has only one route: follow one branch to the bottom, then come back and take the next. What differs between the three DFS traversals is when the node itself is visited, relative to its two subtrees. Visit it first and you get preorder (root, left, right). Visit it between the two subtrees and you get inorder (left, root, right). Visit it last and you get postorder(left, right, root). Left always comes before right; that part is just the convention. The fourth traversal is breadth-first search (BFS), or level order: the whole first level, then the whole second, always left to right. It never dives, and it is driven by a queue (chapter 5). Run each of the four once:
| Traversal | Order | Typical use, and why | Time | Extra space |
|---|---|---|---|---|
| Preorder preorder | root → left → right | Copying or serializing a tree. The root must be written first, so the reader knows what the later nodes hang from. | O(n) | O(h) call stack |
| Inorder inorder | left → root → right | On a BST it produces the values in ascending order — the opening line of the next chapter. | O(n) | O(h) call stack |
| Postorder postorder | left → right → root | Finish the children before finishing me: computing height, deleting or freeing a whole tree, any bottom-up problem. | O(n) | O(h) call stack |
| Level order level-order | level by level, left to right | Output per level, and anything shallowest-first: BFS reaches a node at the smallest possible depth first. | O(n) | O(w) queue |
Two anchors, and why we write O(h) and not O(log n)
First anchor: the name of a DFS traversal describes when the root is visited — pre, in, post. Left is always before right, in all three. Second anchor: DFS spends its extra space on a stack (the call stack, or one you manage yourself), so it is O(h), where h is the height of the tree. Write O(h), not O(log n). h is about log n only when the tree is balanced; it is n−1 when the tree degenerates into a chain. BFS spends its extra space on a queue, so it is O(w), where w is the number of nodes on the widest level. For a perfect tree of one million nodes, h is about 20 while w is about 500,000 — four orders of magnitude apart, on the same tree.
Writing them yourself: three DFS traversals, an iterative preorder, and a BFS
The recursive versions are the definition typed out. The iterative version shows what the recursion was doing: managing a stack.
Compare the three recursive functions. Only one line moves: the line that outputs the node sits before, between, or after the two recursive calls. The route is identical in all three. The iterative preorder then makes the hidden stack visible: it keeps its own stack of nodes still to be handled, and pushes the right child first, because a stack returns the item pushed last — pushing left second is what makes left come out first. The level-order function at the bottom records size before the inner loop; §07 explains why that single line is what separates one level from the next.
sys.getrecursionlimit() is about 1000 by default, so a chain of 1000 nodes is enough to hit it. The LeetCode Python environment raises the limit for you, but you need to know this when you run code locally and when you answer out loud in an interview.The interview question: recursive or iterative?
A complete answer: the recursive version reads like the definition of the tree, and its cost is a limited stack depth (Python about 1000 by default; JVM and JS engines a few thousand to a few tens of thousands of frames). A very deep or chain-shaped tree needs the iterative version, whose depth is limited by heap memory instead. Both are O(n) time. Being able to write the iterative preorder without hesitating is worth points. If the interviewer asks for O(1) extra space, the answer is Morris traversal: it borrows the unused right pointers of nodes to remember where to return, so it needs no stack at all. It does modify the tree while it runs, and restores every pointer it changed before it finishes.
Three languages: you always build the tree yourself
None of the three ships a binary tree. Three versions of TreeNode, plus one helper that builds a tree from a LeetCode array.
Arrays and dictionaries come with every language; trees do not. The shape of a tree is decided by the problem, so a standard library cannot supply a general one. (Java’s TreeMap is a red-black tree inside, but it does not expose the nodes.) The good news: when you solve problems, the TreeNode class is given to you and you only have to read it. For testing on your own machine, the buildTree below turns a LeetCode level-order array such as [3,9,20,null,null,15,7] into a real tree:
is None, not not vals[i]. The second form also treats the perfectly legal node value 0 as empty, and that is a real source of wrong answers.| Topic | Java | Python | JavaScript |
|---|---|---|---|
| Node definition | class TreeNode with fields and a constructor | class TreeNode with default arguments in __init__ | class or a constructor function, both work |
| Empty tree / missing child | null | None (test with is None) | null (test with ===) |
| Queue for level order | ArrayDeque / LinkedList | collections.deque | An array plus a head index (do not use shift) |
| Recursion depth limit | Thread stack 512 KB to 1 MB (tunable with -Xss) | About 1000 by default (sys.setrecursionlimit) | Engine dependent, on the order of ten thousand frames |
The plan for tree problems: this node, plus the two answers below it
★ Interview coreTwo recursive styles cover almost everything. Four problems, frame by frame.
Tree problems vary a lot, but the skeleton is one sentence: the answer for a tree = what this node contributes + the answer for the left subtree + the answer for the right subtree. So the first question is always the same: if the answers for the two subtrees were already in my hand, how would I build the answer for the whole tree? Once you can state that combination, add the base case and the code is finished. What differs between problems is the direction the information travels, and that gives two styles:
Information flows from the root toward the leaves. Whatever the ancestors already established — the current depth, the remaining sum, the path so far — is carried down in a parameter. The work happens at the preorder position, on the way in, and the result is decided at a leaf. See LC 112, 257, 129.
Information flows from the leaves toward the root. The two recursive calls return first, and this node combines their return values into its own answer at the postorder position, on the way out: height, node count, diameter. See LC 104, 110, 543, 124, 236.
How to choose: if the answer depends on the ancestors (how deep am I? what is the sum so far?), pass state down. If it depends on the descendants (how tall is the subtree below? how many nodes?), collect return values on the way up. When you are not sure, try bottom-up first; most tree problems have that shape.
One warning about the bottom-up style: the value the function returns is not always the answer you want. The classic case is the diameter (LC 543 in the problem set): the function returns a height, because that is what the parent needs, while the diameter is tracked in a separate variable that every node challenges as it finishes. Whenever a problem asks for something that can bend at a node, expect these two to differ, and state both explicitly before writing code.
LC 104 · Maximum Depth of Binary Tree
EASYThe problem: return the maximum depth of the tree. Read the convention first: LeetCode counts nodes on the longest path from the root down to a leaf, so a single node has maximum depth 1 and the empty tree has 0. That is one more than the edge-counting depth defined in §01, where the root has depth 0. Both conventions are common; always say which one you mean.
The promise: maxDepth(node) returns the number of nodes on the longest path from node down to a leaf. The base case: maxDepth(null) = 0. The combination: 1 + max(left answer, right answer) — the node itself adds one level, and only the deeper side can decide the longest path. Three questions answered, so the function is written. This is the first bottom-up problem in the chapter:
Complexity and follow-ups
Every node is visited once, so the time is O(n). The call stack is as deep as the tree, so the extra space is O(h): about log n when the tree is balanced, and n when it is a chain. Follow-up one: “do it with BFS.” Traverse level by level and count the levels; the number of levels is the depth. Follow-up two: “what about the minimum depth?” Watch the leaf trap (LC 111 in the problem set): a node with only one child is not a leaf, so the empty side must not contribute its 0.
LC 226 · Invert Binary Tree
EASYThe problem: mirror the whole tree from left to right. The promise: invertTree(node) returns the same subtree, mirrored. The base case: an empty tree returns null. The combination: swap the two child references of this node, and let the recursion mirror each subtree. What the swap writes is two references (§02), so one assignment moves a whole subtree; the ordering inside each subtree is the job of the recursion. Swapping before or after the two recursive calls produces the same tree:
A well-known interview story
Max Howell, the author of Homebrew, the package manager most Mac developers use, was turned down by Google and posted about it. He said the company told him that although the large majority of their engineers use his software, he could not invert a binary tree on a whiteboard. That post is why LC 226 became the most famous Easy problem on the site. You can write it now, and you can also say that it costs O(n) time and O(h) space, and that what gets swapped is references rather than values.
LC 101 · Symmetric Tree
EASY+The problem: decide whether a tree is a mirror of itself. The difficulty: being symmetric is not a property of one subtree. It is a relation between the left subtree and the right subtree, and a function of a single node cannot express a relation between two. The fix: give the recursion two parameters, check(L, R). The promise: check(L, R) returns true when subtree L and subtree R are mirror images of each other. The base cases: both null is true; exactly one null is false. The combination: the values must be equal, and L.left must mirror R.right (the outer pair) and L.right must mirror R.left (the inner pair). Two pointers walk the two halves in mirrored steps:
Complexity and follow-ups
O(n) time and O(h) stack space. The transferable idea: a recursive function does not have to take a single node. Walking two trees at once is what LC 100 (same tree), this problem, and LC 572 (subtree of another tree) all rely on. Follow-up: “write it iteratively.” Put the pairs (L, R) that should be compared into the container in pairs, and take out one pair per round. A stack or a queue both work; keeping the two nodes together is the part that matters.
LC 102 · Binary Tree Level Order Traversal
MEDIUMThe problem: return the values level by level, one array per level ([[3],[9,20],[15,7]]). What we already know: a queue hands out the nodes in level order, but as one flat sequence. Where is the boundary between levels? The step that answers it: at the moment a level begins, the queue holds exactly the nodes of that level and nothing else. So record size = queue length first, and dequeue exactly that many nodes this round. The children enqueued during the round line up behind them and belong to the next level. Without the recorded size the loop cannot tell where the level ends, because the queue keeps growing while you read it:
Complexity, and how far this one line reaches
O(n) time; the queue holds at most one level, so O(w) space. Recording the size first is the step behind zigzag level order (LC 103, reverse every other level), the right side view (LC 199, keep the last node of each level), the largest value on each level (LC 515), and the minimum depth (LC 111, return as soon as a leaf is dequeued). Each one is this template with two lines changed. Once you have this problem, BFS on trees is complete.
Problem set: 11 binary tree problems
Hot 100 selectionEasy to hard: two-tree recursion, the two styles, BFS, construction, ancestors, ending with LC 124.
Quiz
✎ QuizEight questions. Get them all right to light up this chapter.
Which statement about depth and height is correct? (Counting edges, the usual convention.)
Which is the correct definition of a complete binary tree (完全二叉树)?
A small tree: root 4, left child 2 (whose children are 1 and 3), right child 6. What does its inorder traversal print? (Separate the numbers with spaces or commas.)
A recursive function has no base case. What happens when it runs?
Level-order traversal (BFS) needs which helper data structure, and why?
For a binary tree with n nodes, what is the possible range of the height h? (Counting edges.)
What is the real difference between the top-down and bottom-up recursive styles?
Given only two traversal sequences, which combination determines a binary tree uniquely?
- The sentence the chapter rests on: a tree is either empty, or a root plus a left subtree and a right subtree. The structure is defined recursively, so the code that handles it is recursive too.
- Three questions for every recursion: what does it promise to return, what is the base case (on a tree, the empty tree, on the first line), and how is this answer built from the children answers. Every call must be strictly smaller, or the base case is never reached and the stack overflows (Python allows about 1000 frames by default).
- Preorder, inorder, and postorder are the same DFS route; the name says only when the node itself is visited. Level order is BFS. All four are O(n) time. DFS uses O(h) stack space, which is log n only when the tree is balanced and n when it is a chain; BFS uses O(w) queue space.
- Two styles: top-down carries ancestor information down in a parameter (path sum, depth); bottom-up carries subtree information up in a return value (height, diameter). Choose by asking whether the answer depends on ancestors or on descendants. And remember that the returned value is not always the answer: LC 543 returns a height while the diameter is tracked separately.
- The step that makes BFS work level by level: record the queue size before the inner loop and dequeue exactly that many nodes. The right side view, zigzag level order, and minimum depth are all variations of it.
- The three shape names, which do not translate the way you would guess: full (真二叉树) means every node has 0 or 2 children; perfect (满二叉树) means every level is filled, so all leaves share one depth; complete (完全二叉树) means every level is filled except possibly the last, which fills from left to right. Only a complete tree maps onto an array with no waste, children of index i at 2i+1 and 2i+2 — that is the basis of the heap in chapter 09.
- Rebuilding a tree from traversals: preorder + inorder, or postorder + inorder (the first identifies the root, the inorder splits left from right). Preorder + postorder is not enough, because a node with a single child looks the same either way. With n nodes the height ranges from ⌊log₂ n⌋ to n−1, and forcing it to stay near the low end is the motivation for the next chapter.