Explore tree interview patterns with interactive DFS, BFS, binary search tree and path sum problems. Follow each step and study Python solutions.
The pattern
Trees: solve it for one node, recurse for the rest
A binary tree is a node with up to two children, each the root of a smaller tree. Almost every tree problem is a depth-first search where you decide what happens at a single node, or a breadth-first search when the question is about levels. The real work is choosing what each call returns (bottom-up) or receives (top-down).
1A node plus two smaller trees
Every subtree is a tree too. So most solutions decide what to do at one node and let the same function handle the left and right subtrees, down to the empty tree.
2Answers up, or information down
Bottom-up: each node combines its children's answers (depth, height, best path). Top-down: each node passes something to its children (the max so far, a valid range).
3Depth first or breadth first
DFS (recursion or a stack) finishes one branch before the next. BFS (a queue) goes level by level, which is what “per level”, “nearest” and “right side” questions want.
How to spot which kind
- Combine the children's answers (depth, height, diameter, path sum): post-order DFS returning a value.
- Depends on the path from the root (good nodes, valid ranges): pass it down as an argument.
- Levels, “nearest”, “seen from the side”: BFS with a queue, one level per round.
- A BST: compare with the node and go one way, like binary search; in-order visits it sorted.
Reading the pictures
- Nodes are placed left to right in in-order, so a binary search tree reads as a sorted row.
- Blue text beside a node is what it returns or carries (↑ a height, a valid range); orange text under a node names a pointer.
- Inputs use LeetCode's level-order format, e.g. [3,9,20,null,null,15,7]. For the traversals themselves, see the Binary Tree Traversal page.
NeetCode 150 · Trees
All 15 problems
Pick a problem to see it solved step by step. They're in NeetCode's order, roughly easiest first.
Invert Binary Tree
EasyBlind 75Mirror a binary tree: swap the left and right child of every node, and return the root.
root = [4,2,7,1,3,6,9]
variables
- nodes swapped
- 0
Press Play or Step to watch the solution run.
Brute force vs the pattern
On this input:
- Pattern: O(n)
- 7 ops
- Brute force
- n/a
There's nothing slower worth trying: every node has to be visited once to swap its children, so O(n) is the best possible.
“ops” counts basic steps: lookups, inserts, comparisons, array reads. On tiny inputs brute force can even win, because it may stumble on the answer early; as n grows, the gap opens up.
How it works: Invert Binary Tree
Step by step
- Node being swapped
- Already swapped
Press Start or Step: the step the animation is on lights up below.
- 1
Start at the root
def invert(root): - 2
Swap the children, recurse
root.left, root.right = root.right, root.left; invert(root.left); invert(root.right) - 3
Return the root
return root
A tree is a node plus two smaller trees. To mirror it, swap the node's two children, then mirror each child's subtree the same way.
That's the recursive pattern behind almost every tree problem: decide what to do at one node, and trust the recursion for the subtrees. BFS with a queue works just as well.
Spot it in an interview
- “Do something to every node” where each node's work only needs the node itself: any traversal order works.
- The warm-up for thinking recursively about trees.
One visit per node; the recursion stack is as deep as the tree (h).
Credits
Learn more from NeetCode
The problem list and order come from the NeetCode 150 by NeetCode (neetcode.io). The solutions here follow the approaches NeetCode teaches in the linked videos; the animations, explanations and code were written for CodeQuest. If these help, NeetCode's videos and site are well worth your time.
Problem statements are summarised in our own words; the full versions are on LeetCode.