DSA Patterns Made Simple · Trees and Graphs
Tree DFS: Let Recursion Do the Work
Most tree problems are three lines of recursion: handle the empty tree, ask both children, combine their answers. Learn to trust the recursion and depth, inversion and BST checks become easy.
The problem
Maximum Depth of Binary Tree: how many levels does a tree have? You could track levels with a loop and a queue, but there's a one-line idea: a tree's depth is 1 + the deeper of its two subtrees.
How to spot it
- Input is a binary tree (or any tree)
- The answer for a node can be built from the answers for its children: depth, size, sum, "is balanced", "is mirrored"
- Paths from root to leaf ("path sum", "all root-to-leaf paths")
- Validate a binary search tree, find the lowest common ancestor
The idea
Write a function that answers the question for one node, assuming it already works for the children:
- Base case: the empty tree (
None/null). What's the answer for nothing? (Depth 0, sum 0, "valid".) - Ask the children: call the function on
leftandright. - Combine: build this node's answer from theirs.
Don't trace the whole recursion in your head. Check the base case and one combine step; if both are right, the whole thing is right. It's like a manager asking two team leads for their head counts and adding one for themselves.
When information must flow down (allowed value range in a BST, path so far), pass it as extra parameters.
The template
def solve(node):
if node is None:
return BASE # answer for the empty tree
left = solve(node.left)
right = solve(node.right)
return combine(node.val, left, right)
function solve(node) {
if (node === null) return BASE; // answer for the empty tree
const left = solve(node.left);
const right = solve(node.right);
return combine(node.val, left, right);
}
Worked example
Depth, mirror (invert), and BST validation, where the allowed range is passed down to each child.
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def build(values):
"""Level-order list (None = no child), like the pictures in problem statements."""
nodes = [Node(v) if v is not None else None for v in values]
kids = nodes[1:]
for node in nodes:
if node:
node.left = kids.pop(0) if kids else None
node.right = kids.pop(0) if kids else None
return nodes[0] if nodes else None
def max_depth(node):
if node is None:
return 0
return 1 + max(max_depth(node.left), max_depth(node.right))
def invert(node):
if node is None:
return None
node.left, node.right = invert(node.right), invert(node.left)
return node
def in_order(node):
return in_order(node.left) + [node.val] + in_order(node.right) if node else []
def is_bst(node, low=float("-inf"), high=float("inf")):
if node is None:
return True
if not (low < node.val < high):
return False
return is_bst(node.left, low, node.val) and is_bst(node.right, node.val, high)
tree = build([3, 9, 20, None, None, 15, 7])
print("depth:", max_depth(tree))
print("in order before:", in_order(tree))
print("in order after invert:", in_order(invert(tree)))
print("valid BST [2,1,3]?", is_bst(build([2, 1, 3])))
print("valid BST [5,4,6,None,None,3,7]?", is_bst(build([5, 4, 6, None, None, 3, 7])))
Output
depth: 3 in order before: [9, 3, 15, 20, 7] in order after invert: [7, 20, 15, 3, 9] valid BST [2,1,3]? True valid BST [5,4,6,None,None,3,7]? False
class Node {
constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }
}
function build(values) {
// Level-order list (null = no child), like the pictures in problem statements.
const nodes = values.map((v) => (v === null ? null : new Node(v)));
const kids = nodes.slice(1);
for (const node of nodes) {
if (node) {
node.left = kids.length ? kids.shift() : null;
node.right = kids.length ? kids.shift() : null;
}
}
return nodes[0] ?? null;
}
function maxDepth(node) {
if (node === null) return 0;
return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}
function invert(node) {
if (node === null) return null;
[node.left, node.right] = [invert(node.right), invert(node.left)];
return node;
}
function inOrder(node) {
return node ? [...inOrder(node.left), node.val, ...inOrder(node.right)] : [];
}
function isBst(node, low = -Infinity, high = Infinity) {
if (node === null) return true;
if (!(low < node.val && node.val < high)) return false;
return isBst(node.left, low, node.val) && isBst(node.right, node.val, high);
}
const show = (v) => JSON.stringify(v).replaceAll(",", ", ");
const py = (b) => (b ? "True" : "False");
const tree = build([3, 9, 20, null, null, 15, 7]);
console.log("depth:", maxDepth(tree));
console.log("in order before:", show(inOrder(tree)));
console.log("in order after invert:", show(inOrder(invert(tree))));
console.log("valid BST [2,1,3]?", py(isBst(build([2, 1, 3]))));
console.log("valid BST [5,4,6,None,None,3,7]?", py(isBst(build([5, 4, 6, null, null, 3, 7]))));
Output
depth: 3 in order before: [9, 3, 15, 20, 7] in order after invert: [7, 20, 15, 3, 9] valid BST [2,1,3]? True valid BST [5,4,6,None,None,3,7]? False
The second BST fails even though every parent is bigger than its left child and smaller than its right child: 3 is a fine left child of 6, but it sits in 5's right subtree and is smaller than 5. Passing the allowed range down catches that.
Common mistakes
- Missing the base case, which crashes on
None.leftor recurses forever. - Checking only parent and child in a BST. Every node must respect all its ancestors; pass
lowandhighdown. - Swapping in two steps when inverting (
node.left = invert(node.right)thennode.right = invert(node.left)uses the already-changed left). Swap together. - Very deep trees. A tree shaped like a linked list with 100,000 nodes can exceed the recursion limit; use an explicit stack.
Practice
- Maximum Depth of Binary Tree (easy)
- Invert Binary Tree (easy)
- Validate Binary Search Tree (medium)
- Lowest Common Ancestor of a BST (medium): if both values are smaller, go left; both bigger, go right; otherwise you're at the split point.
Key points
- Base case for the empty tree, ask both children, combine.
- Trust the recursion: verify the base case and one step.
- Pass constraints down as parameters (BST ranges, path so far).
- O(n) time; O(h) stack space for a tree of height h.
Practice questions
Why isn't 'left child < parent < right child at every node' enough to validate a BST?
Answer
A BST requires every node in the left subtree to be smaller than the node and every node in the right subtree to be larger, not just the direct children. A grandchild can satisfy its parent but violate an ancestor, so pass the allowed (low, high) range down.
What is the space complexity of recursive tree DFS?
Answer
O(h), where h is the tree height, for the call stack: O(log n) for a balanced tree, O(n) for a degenerate one.
Open in the app to mark lessons complete, take notes and track your progress.