Foundations — Binary tree — structure, traversals - preorder, inorder, postorder (recursive and iterative)

This page assumes you have seen nothing. Before you can read the parent note comfortably, every word, arrow, and symbol it uses must first mean something concrete to you. We build them in an order where each one leans only on the ones before it.

1. A "node" — the value-box

Picture a labelled box. Inside it: the value. Sticking out of it: up to two arrows, one pointing down-left, one pointing down-right. If an arrow points to nothing, we draw it as ✗ (empty).

Why the topic needs this. The entire chapter is "visit every node." If you do not have a crisp mental image of one node — a value plus two outgoing arrows — the phrases node.left and node.right in the code are meaningless. Everything is built out of this one brick.

In code the box is:

class Node:
    def __init__(self, val):
        self.val = val     # the value inside the box
        self.left = None   # the down-left arrow (points to a Node or to nothing)
        self.right = None  # the down-right arrow

2. None / null — the "arrow points to nothing"

Picture the ✗ from the previous figure. That ✗ is None. It is not a box with the value zero; it is the absence of a box.

Why the topic needs this. None is the stopping signal for everything recursive. The very first line of every traversal is if node is None: return. If you think None means "a box holding nothing," you will try to read None.left and crash. None means no box at all.

3. Root, parent, child, leaf — family words

Once boxes point to boxes, we get a family. The words below are just names for positions in that family.

Why the topic needs this. The traversal orders are described entirely in these words: "visit the parent before its children" (preorder), "between its children" (inorder), "after its children" (postorder). Without knowing which box is parent vs child, the sentence has no meaning.

4. "Subtree" — a child is itself a whole tree

This is the single most important idea, so it gets its own figure.

Look at the figure. The whole thing is a tree with root 1. But draw a loop around box 2 and everything below it — that loop contains a perfectly good little tree with root 2. That is the left subtree of 1. The single box 3 (with two None arrows) is the right subtree of 1, also a valid tree.

Why the topic needs this — this is the heart of everything. Because a child's subtree is the same kind of thing as the whole tree, the exact same procedure works on it. This is called self-similarity. It is why recursion (next section) fits trees perfectly: "traverse the tree" = "visit root, then traverse the left subtree the same way, then traverse the right subtree the same way." The problem shrinks but never changes shape.

5. Recursion — a rule that calls itself

Two mandatory parts:

1. Base case — the smallest input, answered with no further calls. For trees this is if node is None: return (an empty tree needs zero work — you are done).
2. Recursive step — reduce to smaller sub-problems (the left subtree and the right subtree) and call yourself on each.

See Recursion and the Call Stack for the machinery. The key visual: each call waits for its inner calls, so calls nest like Russian dolls.

6. The call stack — how recursion remembers

The stack grows downward into the tree (one saved frame per level you descend) and shrinks as you climb back up. The figure shows the stack holding exactly the chain of ancestors from the root to where you currently are — never more.

Why the topic needs this. Two reasons:

• It explains the space cost $O(h)$ (see §8): at any instant the stack holds only one box per level, so its maximum height equals the tree's height $h$.
• The iterative traversals in the parent note replace this hidden stack with an explicit Stack (LIFO) you build yourself. To understand why iterative preorder pushes the right child before the left, you must first see that a stack is LIFO — Last In, First Out — the last thing pushed is the first popped.

7. Big-O notation — measuring cost

Symbols you will meet:

Why the topic needs this. The parent states Time $=O(n)$ (each box is touched a constant number of times) and Space $=O(h)$ (stack depth). Those statements are unreadable unless $n$, $h$, $O$, and $\log$ each already mean something.

8. Balanced vs skewed — the two extremes of $h$

This is exactly why the parent says balanced traversal uses $O(\log n)$ stack space but a skewed tree uses $O(n)$. Same algorithm, cost set by the shape. More in Tree Height and Balance.

How these feed the topic

Everything on the left must be solid before the three traversals on the right make sense. The two paths — recursion (hidden stack) and iteration (explicit Stack (LIFO)) — meet at the same result.

Where these lead next

• Binary Search Tree — a tree where left < node < right, so inorder comes out sorted.
• Level-order Traversal (BFS) — visiting level by level using a queue instead of a stack.
• Construct Tree from Preorder + Inorder — rebuilding the boxes from two traversal lists.

Equipment checklist

Cover the answers. If any line stumps you, re-read its section before the parent note.