• The number of nodes in the tree is in the range [0, 100]
• -100 <= Node.val <= 100
• Return the values as a flat array, in visit order
• Node values are not necessarily distinct

An array lays its items out in a line, so "go through all of them" has one obvious meaning: start at the left end, walk to the right end. A tree has no line. From a node you can go two ways at once, so "go through all of them" needs a decision, and different decisions produce different orderings of the very same nodes. This page is about that decision — and it is worth taking slowly, because almost every tree problem you will ever see is really the question "in what order should I visit, and at what moment should I do my work?" in disguise.

A node is a small box holding a value plus two links, one called left and one called right. Each link either points at another node or points at nothing (null). The whole structure is reached through one entry point, the root. A node with both links empty is a leaf — the end of a branch. Nodes are never allowed to link back upward or sideways, so there are no loops: from the root, every node is reachable by exactly one downward path.

Here is the observation everything else grows from. Take any node and look at what hangs below its left link. It is a node with a value and two links of its own, reachable through a single entry point — that is, it is itself a binary tree, just a smaller one. We call it the node's left subtree. The same holds on the right. So a binary tree is not merely "a bunch of nodes"; it is a value with two smaller binary trees attached. A structure defined in terms of smaller copies of itself is called self-similar, and self-similar structures are exactly what recursion was invented for.

Recursion just means a function that calls itself on a smaller piece of the input. Two parts are needed, and only two:

That second part is where people get stuck, so say it plainly: when you write traverse(node.left), you do not trace what happens inside. You assume it correctly handles the entire left subtree, however big it is, and you move on. This is not hand-waving, it is an induction argument. The base case is correct on its own. Every larger case is correct provided the smaller ones are. Since every call moves strictly downward and the tree is finite, every chain of calls reaches null eventually — so correctness propagates from the leaves back up to the root. Write the base case, write the one honest step, trust the rest.

Underneath, the machine is doing the bookkeeping you refused to do. Each call gets a stack frame — a scrap of memory holding that call's own node and a bookmark for which line it had reached. Calls pile up as you descend and are removed as they finish, so the frames behave like a stack of plates: the last one added is the first one taken off. When a call finishes, the machine pops its frame and resumes the parent exactly where it paused. That automatic pause-and-resume is why "go all the way down the left, then come back up and handle the right" needs no explicit machinery from you.

Now write the only traversal there is. Visit the left subtree, visit the right subtree, and somewhere among those two calls, do your own work:

def traverse(node):
    if node is None:      # base case: empty tree, nothing to do
        return
    # (A) work here — before both children
    traverse(node.left)
    # (B) work here — between the children
    traverse(node.right)
    # (C) work here — after both children

The recursive calls never move. The only freedom in the entire structure is which of the three slots holds your work, and each choice has a name:

That is the entire content of those three intimidating words. Not three algorithms — one algorithm, three positions for a single line.

Same walk, but record in slot (B) instead. At 1 we do not write yet — we descend left first. At 2, still nothing — descend left again. At 4, its left is empty and returns immediately, so 4 writes itself, then its empty right returns. Back in 2, the left subtree is now done, so 2 writes itself, then descends right to 5, which writes itself. Back in 1: left subtree done, so 1 writes itself, then 3 writes itself. Result: 4, 2, 5, 1, 3 — every node sandwiched between its left descendants and its right descendants.

And slot (C): 4 writes after both its empty children, then 5, then 2 (only once 4 and 5 are done), then 3, then finally 1 — the root last, always. Result: 4, 5, 2, 3, 1. Notice pre-order always starts with the root and post-order always ends with it. That is not a coincidence to memorize, it falls straight out of the slot you picked.

Each node is entered exactly once and does a constant amount of work there — a null check, a record, two calls — so the time is O(N) for N nodes: double the tree, double the work. You cannot beat that, since listing every value requires touching every value.

Memory is the more interesting number. At any instant, the frames alive on the stack are exactly the nodes on the path from the root down to where you currently stand, so the peak is the tree's height H: O(H) extra space. For a bushy, balanced tree the height is about log₂N — 20 frames for a million nodes, nothing. But nothing forces a tree to be bushy. A tree where every node has only a left child is one long chain of N nodes; then H = N and the stack holds N frames at once. That worst case is why the very next problem, Iterative Traversals, replaces the hidden call stack with one you build and control yourself.

Train the reflex here, because it pays for the rest of this section: when a tree problem lands, do not ask "which traversal is this?" Ask "what does one node need in order to do its job, and where does that information come from?" Needs something from above → act on the way down, pre-order, and pass the information into the recursive calls as arguments (Path Sum, Binary Tree Paths). Needs something from below → let the calls return values to you and combine them on the way up, post-order (Maximum Depth, Diameter, Balanced Binary Tree). Answer that one question and the code writes itself.