Tree Essentials & Core Mechanics

What is this?

Before doing anything fancy with a tree, you need two everyday skills: how to visit every node in some sensible order, and how to compare two trees or measure one. Think of touring a museum — you can stroll the rooms in different routes, but you still want to see every exhibit exactly once. These problems teach you those reliable walking routes and the habit of checking each node against its neighbors.

💡 Fun fact: The three classic walking orders — preorder, inorder, and postorder — were named by Donald Knuth, who literally wrote the book on these algorithms. On a sorted tree, the "inorder" walk magically spits the values out in perfect sorted order.

🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: Before you can solve a clever tree problem, you need two boring superpowers cold: walking a tree in a chosen order and comparing/measuring it node-by-node. This chapter drills exactly those — and they turn out to be the building blocks every harder tree problem snaps together from.

What this chapter is really teaching

A binary tree is recursive by definition — empty, or a node with a left and a right subtree. So the foundational skill isn't memorizing problems; it's getting fluent with the one template that fits the recursive shape:

def solve(node):
    if not node:                 # 1. base case — the empty tree
        return ...               #    (almost every bug hides in a missing base case)
    L = solve(node.left)         # 2. trust recursion on the smaller trees
    R = solve(node.right)
    return combine(node, L, R)   # 3. do this node's work, fold the results

Three slots: a base case, two recursive calls, and a combine step. Everything in this chapter is a variation on where you do the node's work (the order) and what the combine step computes (a list, a boolean, a number).

The five problems and how they connect

Traversals — the same walk, three timings

The three depth-first orders differ by one thing: when you record the node relative to its children.

• Binary Tree Preorder Traversal — root-first. The natural order for cloning and serializing a tree. (recursive → explicit stack → Morris O(1) space)
• Binary Tree Inorder Traversal — left-root-right. On a BST this streams keys in sorted order — the backbone of an ordered index scan. (recursive → stack → Morris)
• Binary Tree Postorder Traversal — children-before-parent. The order for deletion, bottom-up sizes, and Merkle hashing. (recursive → flag-stack → reversed-preorder trick)
• Binary Tree Inorder Successor — "what's the next node in inorder order?" — i.e. advancing a sorted cursor one step, the way a database index walks to the next key.

Comparison — fold the tree into a yes/no

• Same Tree — walk two trees in lockstep and demand same shape and same value at every position, bailing the instant one disagrees. This is the inner loop of Merkle-tree / replica comparison in distributed databases.

The two cross-cutting skills you'll practice

Recursion vs. iteration (and why both matter)

Interviewers very often follow "write the recursive version" with "now make it iterative." Practicing the explicit-stack form here is what lets you answer that instantly.

The base case is where bugs live

Every recursion needs an honest answer for the empty tree (None). Most tree bugs are a missing or wrong base case — a comparison that crashes on a null child, a traversal that double-counts a leaf. Build the reflex: write if not node first, decide what it returns, then write the rest.

📓 Draw it yourself

Two quick sketches make this whole chapter click:

1. The three orders, one tree. Draw a tiny tree (R) → (L),(Ri) three times. On copy 1 number the nodes in preorder visit order, copy 2 in inorder, copy 3 in postorder. Seeing 1-2-3 land in different spots burns the difference in permanently.
2. Lockstep comparison. Draw two trees side by side and walk a finger down both at once for Same Tree — mark the first position where they'd disagree. That's the early-exit your code performs.

Snap photos of your sketches and embed them in any lesson with the /host-diagrams skill.

Complexity at a glance

Key takeaways

• One template, many problems. Base case → recurse left/right → combine. Get this reflex and traversal, comparison, and successor all fall out of it.
• The three DFS orders differ only in when you touch the node — preorder copies, inorder sorts (on a BST), postorder cleans up.
• Always be ready to go iterative. The explicit-stack form is the standard follow-up; Morris is the "O(1) space" flex.
• Master the base case. Empty-tree handling is where most tree bugs (and most interview points) are won or lost.
• Why this chapter matters: these aren't five trivia problems — they're the moving parts that every later tree problem (LCA, completeness, serialize) is assembled from.

Next: start with the three traversals, then Same Tree — then carry the template into the harder problems in this topic.