Tree Coding Basics

9 concept walkthroughs, each with a worked explanation and an interactive visualization, before you start solving problems in this area.

How a Tree Looks in Code

Trees are nodes connected by references, not drawings

The blueprint: one tiny class, every tree ever

The panel above showed you the TreeNode class, a value plus two pointers. Here is the part that deserves a spotlight: that class is the ENTIRE data structure. There is no Tree class, no drawing, no container holding all the nodes. A tree in code is just TreeNode objects gripping each other through left and right, plus one variable in your hand pointing at the top one.

One naming note before you type real code. This page called the data field value; the lessons ahead and the Code Arena use the LeetCode convention val, with a constructor that can take children directly. Same box, different sticker: get comfortable reading both.

Build this exact 5-node tree by hand

Time to wire something bigger than the 3-node example above. Target: 8 at the top, 3 and 10 below it, 1 and 6 hanging under the 3. Five nodes, five lines. Read each line as an action: make a node, then screw it into this exact socket.

Order matters in exactly one way: root.left must EXIST before you can write root.left.left. Line 4 works because line 2 already put a TreeNode in the left socket. Swap lines 2 and 4 and the build crashes. You would be asking None for its .left.

Now read it back: what is root.left.right?

A dotted expression is a walk. root.left.right means: start at root (8), hop left (3), hop right. You are now standing on the node holding 6, so root.left.right.val is 6. Cover the answers and try two more on the tree above: root.right.val? (10). root.left.left.val? (1).

Now the sharp edge. root.right.left is None. Node 10 has no left child, so that socket holds None, which is a perfectly legal thing to LOOK at. But root.right.left.val explodes with AttributeError: 'NoneType' object has no attribute 'val'. Asking None for anything is the number one tree crash, and it is exactly what base cases exist to prevent. Two concepts from now, dodging it becomes a reflex.

Functions receive a whole tree as ONE argument

How do you hand this 5-node structure to a function? You pass ONE variable: the root. def max_depth(root) receives a single TreeNode, and from that handle it can walk to all five nodes. That is why every tree function in every lesson ahead has the same signature shape, given root, return something.

And here is the payoff that powers the rest of this module: if root is a whole tree, then root.left is ALSO a whole tree, the self-contained 3-subtree holding 3, 1, and 6. Passing node.left to a function hands it a complete smaller tree. Recursion on trees is nothing more than calling yourself on the two smaller trees you are already holding.

The classic mistake: treating the tree like an array

Fresh from the arrays module, your fingers will type tree[0] or len(tree). Both die instantly: a TreeNode is not subscriptable and has no len(). There is no index, and there is no direct teleport to node 6. The ONLY way to reach any node is hopping pointers from the root, one .left or .right at a time.

That constraint sounds like a downside; it is actually the design. Arrays are flat, so one for loop visits everything. Trees branch, so at every node you must handle left AND right. Which is exactly why the next concepts hand you two systematic walking orders, DFS and BFS, instead of a loop.

DFS vs BFS – Coding Mindset

Two ways to traverse: deep first or level by level

Same six nodes, two completely different itineraries

Take one tree and walk it twice. Six nodes: 1 at the top, 2 and 3 below, 4 and 5 under the 2, and 6 hanging right of the 3. DFS starting at 1 produces 1, 2, 4, 5, 3, 6. BFS on the SAME tree produces 1, 2, 3, 4, 5, 6. Same nodes, same pointers: the visiting order is the entire difference between the two code shapes above.

Look where they first disagree: visit number three. DFS's third stop is 4. It committed to the left branch and kept diving. BFS's third stop is 3. It refused to go deeper before finishing the level. Keep this exact tree in your head; the BFS concept two pages ahead traces it again with the queue fully exposed.

DFS by hand: dive, hit bottom, back up

Run the dive out loud. Visit 1, dive left to 2, dive left again to 4. Node 4 has no children, dead end, so back up to 2 and take its OTHER branch: visit 5. Dead end again, back up through 2 to 1, take 1's right branch: visit 3, then dive to 6. Output assembled along the way: 1, 2, 4, 5, 3, 6.

Who remembers where to back up to? The call stack. Every dfs(node) call that has not finished sits frozen in memory, holding its place between its two recursive lines. When dfs(4) returns, the frozen dfs(2) wakes up exactly where it paused and runs its next line, dfs(node.right). You never write backing-up code. The function-call machinery IS the backing-up code.

BFS by hand: a waiting line, not a dive

BFS replaces bravery with bureaucracy. Nodes wait in a queue; you always serve the FRONT, and the served node's children join at the BACK. Start: [1]. Serve 1, children 2 and 3 join → [2, 3]. Serve 2, children 4 and 5 join → [3, 4, 5]. Serve 3, child 6 joins → [4, 5, 6]. Then 4, 5, 6 are served with nothing left to add. Output: 1, 2, 3, 4, 5, 6. Level by level, left to right.

Why does a plain queue automatically produce levels? Because every level-1 node got in line before any level-2 node could exist in it. Level-2 nodes are only discovered while serving level 1. First in, first out means the generations can never cut in front of each other.

Two engines: the stack dives, the queue sweeps

Strip both versions down and only ONE thing differs: the memory structure holding 'nodes I still owe a visit'. DFS keeps them on the call stack: last in, first out, so the newest discovery (the deepest node) is handled first: that is diving. BFS keeps them in a queue. First in, first out, so the oldest discovery is handled first: that is sweeping. Change the container and you change the itinerary; every other line is the same.

Cost: both visit every node exactly once, so both are O(n) time, neither is faster. Memory differs by tree SHAPE: DFS holds one root-to-bottom path at a time, O(height); BFS holds up to one full level, O(width). On our 6-node tree that is at most 3 stacked calls versus at most 3 queued nodes; on a bushy 1000-node tree the bottom level alone can hold around 500 nodes while the height is only about 10.

The decision rule you'll apply in every problem ahead

When a problem hands you a tree, ask what the ANSWER is made of. If it is about levels, distance from the root, or the nearest/shallowest anything: BFS, because the queue meets nodes strictly in distance order. If it is about combining answers from the left and right subtrees. Heights, sums, mirror checks, path values. DFS, because a paused parent call is the perfect place to combine what its children return.

In this course's arena: Level Order Traversal is pure BFS; Maximum Depth, Invert Binary Tree, and Diameter of Binary Tree are pure DFS. When either would work, most engineers default to DFS. The recursive version is three lines and needs no import.

DFS Coding Pattern (MOST IMPORTANT)

The universal skeleton for almost all DFS tree code

The skeleton, upgraded: return answers instead of just visiting

The panel above shows the visiting skeleton. Null check, action slot, two recursive calls. Real problems need one upgrade: the recursive calls should RETURN something, and the parent should combine what comes back. This returning skeleton is the single most reused piece of code in the whole trees track.

Two dials are all you ever tune. Dial 1: what does an EMPTY tree answer, the value returned at the base case. Dial 2: how does one node combine its own value with the two answers arriving from below. Choose the dials; the skeleton does everything else.

Instantiation 1: count the nodes

Dial 1: an empty tree has 0 nodes. Dial 2: my subtree's count is 1 (me) plus the left count plus the right count. Run it on this 4-node tree: 5 at the top, 3 and 8 below, 1 hanging under the 3.

Watch the answers bubble UP. count(1) returns 1 + 0 + 0 = 1. Both its children are None, and the base case answers 0 for each. count(3) returns 1 + 1 + 0 = 2. count(8) returns 1. Finally count(5) returns 1 + 2 + 1 = 4. Each node performs one addition; the total assembles itself on the way back up.

Instantiation 2: sum the values, turn ONE dial

Same tree, new question: the total of all values. Compare the two functions character by character. The only change is that 1 became node.val. Dial 1 stays 0, because an empty tree contributes nothing to a sum; dial 2 now adds my VALUE instead of counting my existence.

The returns this time: 1 from the leaf, then 3 + 1 + 0 = 4 at node 3, then 8, then 5 + 4 + 8 = 17 at the root. One dial turned, a different problem solved. Max depth? Dial 2 becomes 1 + max(left, right). Invert? The combine step becomes a swap. A dozen lesson problems are this skeleton wearing different dials.

'Trust the recursion': what that actually means

When you write the combine line for node 5, count(node.left) does not exist in any finished form yet. The move: assume the call simply returns the correct count of the left subtree (here, 2) and ask only 'what do I do with a correct 2 and a correct 1?'. You reason about ONE node; the identical reasoning then runs at every node automatically.

It is not faith. It is induction you can watch. At the moment count(1) executes, count(5) and count(3) sit frozen on the call stack, each paused mid-addition, waiting for a number. The leaf answers first, the waiters fill in, the root finishes last. You will feel this exact rhythm again in the postorder concept: children report before the parent speaks.

Delete the base case and trace the crash

The most common tree bug is also the most predictable one. Remove the None check from count and follow the calls: count(5) → count(3) → count(1) → count(None). Inside that last call the code asks None.left, and Python stops the show: AttributeError: 'NoneType' object has no attribute 'left'. Not an infinite loop: an instant, guaranteed crash, because EVERY branch of every tree ends in None.

So write the base case first, and phrase it as a question with an answer, not just a stop sign: what should an empty tree return? For count it is 0; for max depth 0; for 'does this value exist' False. If you cannot answer that question, you do not understand the problem yet. Which is the real reason instructors nag about base cases.

Inorder Traversal (Left → Root → Right)

Go left first, then visit the node, then go right

One line's position defines the whole algorithm

Take the DFS skeleton from the previous concept and place the visit BETWEEN the two recursive calls, that single choice is inorder. The entire left subtree first, then me, then the entire right subtree. Below is the collecting form, which appends into a list instead of printing. The shape you will actually submit in the arena.

Read the placement: out.append is sandwiched. Nothing about a node is recorded until every node in its left subtree has been recorded. That wait-your-turn discipline is the whole algorithm. There is nothing else to it.

Hand-trace it on four nodes, pencil ready

The tree: 4 on top, 2 and 7 below, 3 hanging as 2's RIGHT child. Trace with the out list visible. inorder(4) dives left to inorder(2). Node 2 dives left, hits None, returns instantly, so 2 records itself: out = [2]. Then 2's right: inorder(3). Node 3's left is None, so 3 records: [2, 3]; its right is None, done. Node 2 is finished, control returns to 4, which now records: [2, 3, 4]. Finally inorder(7): left None, record 7 → [2, 3, 4, 7].

Notice that 4 waited for TWO nodes before speaking, and 3, one level deeper than 2, still spoke second, not first. Depth does not decide the order; the left-me-right contract does.

The canonical use: BSTs come out sorted

Look again at the output: 2, 3, 4, 7, sorted. Not a coincidence. That tree is a binary search tree (smaller values left, larger values right, at every node), and inorder on ANY BST emits values in ascending order, because left-me-right literally reads 'smaller ones, me, bigger ones' at every node, recursively.

That equivalence is why interviews adore inorder. 'Validate a BST' becomes 'is the inorder output sorted?'. 'Find the kth smallest value in a BST' becomes 'run inorder and stop at the kth append'. And the Construct Binary Tree from Preorder and Inorder lesson leans on inorder's other superpower: in its output, everything to the left of a node's position IS that node's left subtree.

The pitfall: your hands type preorder out of habit

The dangerous bug here is not a crash, it is silence. Slide the append ONE line up, above the left recursion, and the code still runs and still returns four values... in the order 4, 2, 3, 7. That is preorder. On a plain tree nothing looks obviously wrong; on a BST your 'sorted' output is not sorted, and whatever logic sat on top of it quietly breaks.

The insurance costs five seconds: run your traversal on a small BST you know, like this one. Expected 2, 3, 4, 7 but got 4, 2, 3, 7? Your visit line drifted up. Chant it while typing: left... ME... right.

Preorder Traversal (Root → Left → Right)

Visit root first, then left, then right

Visit first, ask questions later

Same skeleton, visit line moved to the TOP: record the node the instant you set foot on it, then explore left, then right. One consequence follows immediately, and every use of preorder flows from it: the root of any subtree appears BEFORE everything else from that subtree. So the first element of the whole output is always the tree's root.

Here is the collecting form. Put it side by side with the inorder code from the previous concept. The three body lines are identical, just reordered. You are not learning three algorithms; you are learning one skeleton and three positions.

Hand-trace it on four nodes

The tree: 1 on top, 2 and 3 below, 4 hanging as 2's LEFT child. Trace: preorder(1) records immediately, out = [1], then dives left. preorder(2) records on arrival: [1, 2], and dives left. preorder(4) records: [1, 2, 4]; both of 4's children are None, so it returns. Node 2 has no right child, so it returns too. Back at 1, dive right: preorder(3) records → [1, 2, 4, 3]. Done.

For contrast, inorder on this same tree says 4, 2, 1, 3. Preorder announces parents on the way DOWN; inorder makes them wait until the left side is finished. Say that difference out loud once, it is worth ten re-readings.

The canonical use: copying and serializing trees

Suppose you must save a tree to a file and rebuild it later. Rebuilding needs parents to exist before their children. You cannot attach node 4 to node 2 if 2 has not been created yet. Preorder hands you nodes in exactly that order: replaying 1, 2, 4, 3 recreates the tree top-down with no dangling child ever waiting for a missing parent.

Record the empty sockets too and the output becomes a complete blueprint: our tree serializes to 1,2,4,N,N,N,3,N,N. Reading it back left to right rebuilds the exact shape. Every N says 'this socket is empty, back up'. The Construct Binary Tree from Preorder and Inorder lesson uses the milder half of this superpower: preorder[0] is guaranteed to be the root, which anchors the entire reconstruction.

The pitfall: plain preorder can't rebuild a tree by itself

Without the None markers, preorder output is ambiguous. Proof by two pictures: a chain (1, then 2 as its left child, then 3 as 2's left child) and a fork (1 with children 2 and 3) BOTH produce preorder 1, 2, 3. If you saved only that list, you cannot know which tree you had, the shape information is gone.

Two standard fixes, both used in real problems: keep the None markers (nine tokens for our four-node tree (the Ns ARE the shape), or pair preorder with inorder) preorder tells you WHO each root is, inorder tells you WHAT lies left and right of it. That pairing is literally the algorithm of the construct-tree lesson ahead.

Postorder Traversal (Left → Right → Root)

Finish children first, then visit root last

Children report first; the root speaks last

Third and final position for the visit line: the BOTTOM, after both recursive calls. A node records itself only when its entire left subtree AND entire right subtree are already recorded. This flips preorder's promise: in postorder output, the root of any subtree comes AFTER everything inside it, so the last element of the whole output is always the tree's root.

The collecting form one more time: three identical body lines, third arrangement. With this one you own the complete set, top, middle, bottom.

Hand-trace it on four nodes

The tree: 1 on top, 2 and 3 below, 4 hanging as 3's LEFT child. Trace: postorder(1) dives left first. Node 2 dives left: None, dives right, None, and only THEN records: out = [2]. Back up to 1, dive right to 3. Node 3 dives left to 4; both of 4's children are None, so 4 records: [2, 4]. Node 3 has no right child, so it records next: [2, 4, 3]. Everything below 1 is finished, so 1 finally speaks: [2, 4, 3, 1].

Root last, exactly as promised. Notice the PATIENCE of node 1: first node touched, last node recorded. That gap (touched early, recorded late) is where postorder's power lives: by the time a node records, it has seen everything below it.

The canonical use: any bottom-up computation

Ask a node: what is your depth? It cannot answer until both children answer. Its depth is 1 more than the taller child's. That dependency IS postorder, even with no out list in sight: both recursive calls happen first, and the 'visit' is the return line that combines them. Most tree functions that RETURN a number are postorder in disguise.

Run it on our trace tree: depth(2) = 1, depth(4) = 1, depth(3) = 1 + max(1, 0) = 2, and depth(1) = 1 + max(1, 2) = 3. Answers flow strictly upward. Children's results exist before the parent needs them, because the combine line sits BELOW the calls. This exact shape is the Maximum Depth of Binary Tree lesson, and Diameter of Binary Tree stacks one extra measurement on top of the same skeleton. Deleting a tree is the same story: free the children first, the parent last.

The pitfall: acting on the parent before the children

Here is a deletion routine that severs pointers top-down. It looks tidy; it loses data. The instant node.left = None runs, the only handle to the ENTIRE left subtree is gone. The recursive call two lines later receives None and does nothing. On our 4-node tree, the buggy delete(1) orphans node 2 immediately and never visits it.

The fix is pure ordering: recurse first, act last. Move the destructive lines below the calls, into the postorder slot. The general rule worth taping to your monitor: if a parent's action DESTROYS or DEPENDS ON what is below it, that action belongs at the bottom of the function.

BFS / Level Order Traversal

Visit level by level using a queue

The production version: a real deque, not pseudo-code

The pseudo-code above says queue.add and queue.remove; here is what you actually type. Python's collections.deque pops from the front in O(1). A plain list also works, the Level Order Traversal lesson uses queue.pop(0) for simplicity, but pop(0) shifts every remaining element one slot left, costing O(n) per pop; deque's popleft() is the habit worth building now.

Two guards matter. The empty-tree check up front, because deque([None]) would crash on the very first popleft. And the if node.left / if node.right checks before appending, so only REAL nodes ever enter the line. Hold onto that second guard. The mistakes concept next door shows exactly how dropping it burns you.

Ring-by-ring trace: watch the queue breathe

Same six-node tree as the DFS-vs-BFS concept: 1 over 2 and 3, with 4 and 5 under the 2 and 6 right of the 3. Write the queue before every pop: [1] → pop 1, push 2, 3 → [2, 3] → pop 2, push 4, 5 → [3, 4, 5] → pop 3, push 6 → [4, 5, 6] → pop 4 → [5, 6] → pop 5 → [6] → pop 6 → [] and the loop ends. out = [1, 2, 3, 4, 5, 6].

Stare at the middle snapshot, [3, 4, 5]: the tail of level 1 stands AHEAD of the freshly arrived level 2. The queue is rarely 'one level'. It is a sliding window straddling two levels, the old generation draining from the front while the new one grows at the back.

The len(queue) freeze: slicing the stream into levels

The loop above yields one flat stream. Fine for 'visit everything', useless for 'give me each level separately'. The trick: at the top of the while loop, the queue holds EXACTLY the current level and nothing else. Freeze that number with size = len(queue), pop exactly size nodes, and everything pushed in the meantime is exactly the next level.

Two-level check on our tree: the loop's second lap starts with queue = [2, 3], so size = 2. Pop 2 (pushing 4 and 5), pop 3 (pushing 6). Stop, the frozen count of 2 is served. level = [2, 3], and the queue now holds [4, 5, 6]: precisely level 2, staged for the next lap. Final result: [[1], [2, 3], [4, 5, 6]]. This is letter-for-letter the loop inside the Level Order Traversal lesson, which writes the freeze inline as for _ in range(len(queue)).

The classic mistake: popping from the wrong end

A deque has two exits, and muscle memory loves the wrong one. queue.pop(): no argument, removes from the BACK, where you have been appending. That is last-in-first-out: you built a stack by accident, and your 'BFS' silently becomes a right-leaning DFS. No crash, no warning: just the wrong order.

Trace the bug on our tree: [1] → pop 1, push 2, 3 → [2, 3] → pop() takes 3, push 6 → [2, 6] → pop() takes 6 → [2] → pop 2, push 4, 5 → [4, 5] → pop 5, then pop 4. Output: 1, 3, 6, 2, 5, 4. Every node visited exactly once, every level scrambled. If a level-order answer ever comes out deepest-first or right-first, check which end you are popping before you check anything else.

Cost, and when the queue is the right tool

Every node joins the queue once and leaves once, and each visit does constant work with a deque: O(n) time, matching DFS exactly. Space is the widest level, O(w), on a bushy tree the bottom level holds about n/2 nodes, so BFS can briefly hold half the tree in line. Compare DFS's O(height): the two traversals trade width for depth.

Reach for the queue when the QUESTION mentions levels or distance: level-order output, right-side view, minimum depth, 'nearest node such that...'. BFS meets nodes strictly in distance-from-root order, so the first match it finds is automatically the closest one. And this exact loop returns in the graphs track, Rotting Oranges spreads ring by ring with the same len(queue) freeze, so the minutes you spent tracing snapshots here pay off twice.

Common Beginner Mistakes

Learn from common errors to avoid them

Four bugs cause almost every tree-code failure

The list above names the sins; this article shows each one's fingerprint in real code: the buggy snippet, the exact symptom, the fix. The symptoms matter as much as the fixes: a crash points to a DIFFERENT bug than a wrong-but-plausible answer, and knowing the mapping turns twenty minutes of confused staring into a ten-second diagnosis.

All four are traced on trees you have already met in this module, so keep the same pencil out.

Bug 1: the missing base case

Familiar from the DFS pattern concept, and listed first because it bites the most. Every branch of every tree ends in None, so the first leaf you recurse past hands None to your function, which then asks None.left and dies: AttributeError: 'NoneType' object has no attribute 'left'. Not an infinite loop: an instant, reliable crash on any non-empty tree.

The fix is two lines; the discipline is WHERE they go. First lines of the function, written before anything else, phrased as the empty-tree answer: 0 for a count, False for a search, None for a build.

Bug 2: mutating the tree mid-recursion

Inverting a tree means swapping every node's children. The buggy version below does it in two sequential assignments, and the second line reads a pointer the first line ALREADY overwrote. Trace it on the 3-node tree 1 over (2, 3): line one sets node.left to the inverted 3. Line two then computes invert(node.left), but node.left is now 3, not 2. Result: BOTH children point at the same 3, and node 2 has vanished from the tree entirely.

Fix: read both old pointers before writing either. Python's tuple swap evaluates the whole right-hand side first, which is exactly the guarantee you need. The Invert Binary Tree lesson uses the equally safe variant: swap the raw pointers first, THEN recurse into both.

Bug 3: computing answers and dropping them on the floor

This one never crashes, which is what makes it evil. The depth function below dutifully recurses into both subtrees... and ignores what comes back. Every call therefore returns its own last line: 1. Deep tree, shallow tree, three-node chain. The answer is always 1, and all that recursion was pure ceremony.

The rule that prevents it: pick a lane. Lane A: RETURN answers up and combine them (depth, count, sum: the value travels through return). Lane B: COLLECT into a list you pass along (the traversals: the value travels into out). The bug is straddling lanes: recursing as if in lane A while never touching the return values. A bare dfs(node.left) statement inside a function that is supposed to return a number is the tell, stop and look.

Bug 4: letting None children into the BFS queue

DFS forgives you for recursing into None, the base case absorbs it. BFS has NO base case; its only defense is the guard before each append. Drop the guards and every leaf pushes two Nones into the line. Trace it on the tree 1 over (2, 3): pops 1, 2, 3 all succeed and out reaches [1, 2, 3]. The traversal LOOKS finished, then the fourth pop returns None and node.val detonates: AttributeError: 'NoneType' object has no attribute 'val'.

Note the cruelty: the crash fires AFTER all the real work succeeded, and the traceback points at the node.val line, two lines ABOVE the actual mistake. When a BFS crashes late with a NoneType error, inspect the pushes, not the pop.

The ten-second diagnosis table

Symptom first, then the suspect. Crash the instant recursion starts → Bug 1. Crash after the output already looks complete, complaining that NoneType has no 'val' → Bug 4. No crash but the answer is a constant like 1 or None → Bug 3. No crash but the tree comes back with repeated or missing nodes → Bug 2. All the right nodes in the wrong ORDER → not on this page at all: that is a drifted visit line (inorder concept) or a wrong-end pop (BFS concept).

Before running any tree function, spend ten seconds on the next concept's checklist, base case? action position? left, right, or both?, and these four bugs mostly never get typed. The lessons ahead (Maximum Depth, Invert Binary Tree, Level Order Traversal) are exactly where you will catch yourself reaching for each fix.

Universal Mental Template

The checklist to use before coding any tree problem

Four questions that write the code for you

Here's a secret about tree problems: they're not one thousand different problems. They're the SAME four-question interview, asked a thousand ways. Answer the four questions and the code assembles itself, because the recursive skeleton never changes; only your four answers get plugged into it.

The questions: (1) What's my BASE CASE. What do I return when the node is None (or a leaf)? (2) What do I do AT this node. Count it, compare it, swap its children, add its value? (3) Do I need to visit LEFT, RIGHT, or BOTH? (4) Does my action happen BEFORE the recursive calls (preorder position), BETWEEN them (inorder position), or AFTER both return (postorder position)?

Watch the checklist solve three real problems

Max depth: Q1, None returns 0. Q2: add 1 for myself. Q3: both sides. Q4, after (I need my children's depths first). Plug in: return 1 + max(left_answer, right_answer). Done: four answers, four lines.

Count all nodes: Q1, None returns 0. Q2: I'm worth 1. Q3: both. Q4, after. Plug in: return 1 + left_answer + right_answer. Same tree: Q1, both None is True, one None is False. Q2: compare the two values. Q3: both, in lock-step pairs. Q4, before (bail out early on mismatch, THEN recurse). Three wildly different-sounding problems, one skeleton, twelve short answers.

Question 4 is secretly the traversal chooser

Notice that Q4's three answers (before, between, after) are literally preorder, inorder, and postorder from the traversal lessons. That's why you learned them: not as trivia, but as the three possible TIMINGS for your action.

The timing follows from what your action NEEDS. Need the children's answers to compute yours (depth, size, diameter)? You must act AFTER, postorder. Need to hand information DOWN before descending (remaining target in Path Sum, valid range in Validate BST)? Act BEFORE: preorder. Need sorted order out of a BST? BETWEEN: inorder. When you're stuck on a tree problem, asking 'what does my action need?' almost always un-sticks you.

Dry-run the checklist before you trust it

Before running any tree code, sanity-check your four answers on the smallest inputs imaginable. It takes thirty seconds and catches most bugs. Test 1: the empty tree (root is None). Your base case IS the whole answer, does it make sense? Depth 0, count 0, same-tree True. Test 2: a single node. The recursion fires twice on None children and combines. A one-node tree should give depth 1, count 1.

If either micro-test feels wrong, the bug is in your Q1 or Q2 answer, and you found it before writing a single test case. This habit, smallest input first, is the tree equivalent of the DP track's 'hand-verify the base cases', and it will save you in every Code Arena ahead.

Your pocket card for the whole track

Every problem in the Trees track ahead: inversion, symmetry, path sums, diameter, LCA, BST validation, even rebuilding a tree from traversals. Is this checklist wearing a costume. When a problem statement feels overwhelming, don't stare at it; interrogate it with the four questions, write the skeleton, and fill in the blanks.

And when you eventually reach Graphs, the skeleton generalizes: base case becomes the visited-check, 'left and right' becomes 'all neighbors', and Q4's timing question becomes pre/post-order on the traversal. Master this card once, cash it forever.

All DSA learning paths