What Is a Leaf Node? Trees, Base Cases, and Interview Patterns

Every binary tree problem eventually bottoms out somewhere. That somewhere is a leaf node. And the definition is so simple you'll feel embarrassed the first time a subtle leaf-check bug tanks your Path Sum solution in front of an interviewer.

A Leaf Node Has No Children

That's it. Both left and right point to null. No subtrees. Nothing below. The recursion's last stop.

def is_leaf(node):
    return node.left is None and node.right is None

In a general tree where nodes can have any number of children, same idea: a leaf is any node whose children list is empty.

You've been using this concept for years without naming it. Every time you stare at a recursive tree function and ask "what do I return when there's nothing left?", you're asking about leaf nodes. You already knew this. You just weren't charging for it.

One Child Still Isn't a Leaf

Take a small binary search tree:

In this tree, nodes 1, 4, and 9 are leaves. Node 3 has two children. Node 8 has one child. Neither qualifies.

Both children must be null, not just one. A node with a single child is an internal node, and no amount of squinting changes that. This sounds obvious until you're on interview problem 4 of 4 and Path Sum is quietly returning wrong answers and you have no idea why.

The "one child" trap shows up constantly. A path must run all the way from root to a leaf. If you forget to check both pointers, you'll count paths that terminate at node 8 instead of at node 9, and congratulations, you've invented a slightly different problem.

How Many Leaves Does a Tree Have?

Depends entirely on the tree's shape, which is one of those answers that's technically correct and deeply unsatisfying.

In a perfect binary tree (every level fully filled), exactly half the nodes are leaves. Seven nodes gives four leaves. Fifteen nodes gives eight. Very tidy.

In a skewed tree (every node has exactly one child), there's exactly one leaf at the bottom. Might as well be a linked list wearing a trenchcoat.

Algorithms that process only leaf nodes run in O(leaves) time, which is O(n) worst case but often much less. When someone asks you to "find all root-to-leaf paths," the number of such paths equals the number of leaves. That's somewhere between 1 and n/2, which is the kind of range that makes the analysis feel like a shrug emoji.

Why Your Base Case Should Know About Leaves

The most common place you'll meet leaf nodes in interviews is as the base case of a recursive tree function.

Classic example: sum all leaf node values.

def leaf_sum(node):
    if node is None:
        return 0
    if node.left is None and node.right is None:
        return node.val
    return leaf_sum(node.left) + leaf_sum(node.right)

There are two base cases here. The null check handles falling off the tree. The leaf check handles the actual terminal nodes. These are different things. A null node doesn't have a value. A leaf node does. Conflating them is the mistake.

If you need a refresher on base cases in recursion, that post covers why they matter and how to spot them.

The leaf check short-circuits the recursion. Without it, the function still works, technically, but you'd make two unnecessary recursive calls from every leaf, both immediately returning 0. Not catastrophic. Just a little embarrassing.

For height, the leaf check is implicit:

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

A leaf makes two recursive calls that both return 0, contributing 1 to the height. Both styles (explicit leaf check vs. null-fallthrough) are valid. Knowing when each is cleaner is a sign of fluency. Interviewers notice.

Where the Leaf Node Check Bites You in Interviews

Path Sum (LeetCode 112). Given a binary tree and a target sum, find if there's a root-to-leaf path that sums to the target. The leaf check is the entire termination condition, which means forgetting it produces a solution that passes most test cases and fails the ones that matter.

def has_path_sum(node, target):
    if node is None:
        return False
    if node.left is None and node.right is None:
        return node.val == target
    return (has_path_sum(node.left, target - node.val) or
            has_path_sum(node.right, target - node.val))

Without the leaf check, you'd return True for paths that stop at any node whose running sum matches the target. That's a genuinely different problem. It has a different name. You solved the wrong one.

Minimum Depth (LeetCode 111). The minimum depth is the shortest path from root to the nearest leaf. This one has a trap, and it's the kind of trap that feels unfair the first time you hit it.

def min_depth(node):
    if node is None:
        return 0
    if node.left is None and node.right is None:
        return 1
    if node.left is None:
        return 1 + min_depth(node.right)
    if node.right is None:
        return 1 + min_depth(node.left)
    return 1 + min(min_depth(node.left), min_depth(node.right))

If you write only the last line without the one-child guards, you'll return 1 for any node that has only a right child, because min_depth(None) returns 0. A path through null is not a path to a leaf. The problem says "nearest leaf," and null is not a leaf, no matter how many times you wish it were.

Minimum depth catches candidates off guard precisely because maximum depth doesn't have this issue. max(0, some_depth) always picks the real answer. min(0, some_depth) silently picks the wrong one. The asymmetry is genuinely sneaky and not a sign that you're bad at trees. It's a sign that min and max behave differently with 0. You know this now.

Sum of Left Leaves (LeetCode 404). Find the sum of all left leaves. You need to track whether a node is a left child, which means passing that context down through the recursion:

def sum_of_left_leaves(root):
    def dfs(node, is_left):
        if node is None:
            return 0
        if node.left is None and node.right is None:
            return node.val if is_left else 0
        return dfs(node.left, True) + dfs(node.right, False)
    return dfs(root, False)

Both conditions must hold simultaneously: leaf and left child. Neither alone is enough. A right leaf counts for nothing here. A left internal node counts for nothing. Welcome to problems where the definition matters twice.

Tries Work Differently

In a trie, a leaf node carries different semantics. A trie node marks the end of a word with an is_end flag, not necessarily by having no children.

Consider inserting "cat" and "cats." The node for 't' in "cat" is not a structural leaf. It has a child 's'. But it's an end-of-word node. When implementing trie problems, keep structural leaves and semantic endpoints distinct. A node can be end-of-word with children, end-of-word without children, or internal with no flag. Each combination behaves differently and each one will find a way to break your solution if you're not paying attention.

Stack Depth Is Not Leaf Count

When you recurse down a tree to reach leaves, the call stack holds one frame per node on the path from root to the current node. The maximum depth of that stack is the height of the tree, not the number of leaves.

For a balanced tree, height is O(log n). For a skewed tree, height is O(n). Leaf count has nothing to do with stack depth. The recursion space complexity post goes deeper on how to count frames across different tree shapes.

The recursion terminates at leaves because that's where the base case fires. But the space consumed is determined by how deep those leaves are. Interviewers ask about this distinction constantly, and if you can explain it clearly out loud while you're already thinking about the algorithm, you're ahead of most candidates.

Practicing that skill out loud, with feedback, is what SpaceComplexity is built for.

Quick Reference

• Leaf: node.left is None and node.right is None
• Always null-check before leaf-checking (null is not a leaf)
• Root-to-leaf paths terminate at leaves, not at one-child nodes
• Minimum depth requires guarding against one-child nodes; maximum depth does not
• Tree height controls stack depth, not leaf count

Further Reading

• Binary Tree - Wikipedia
• LeetCode 112: Path Sum
• LeetCode 111: Minimum Depth of Binary Tree
• Tree (data structure) - Wikipedia
• Introduction to Tree Data Structure - GeeksforGeeks