What Is a Full Binary Tree? Every Node Has Zero or Two Children

You've written tree traversals. You've inverted binary trees. You know what a heap is.

Then an interviewer says "is this a full binary tree?" and suddenly you're not sure if you know what "full" means.

A full binary tree has exactly one rule: every node has either zero children or exactly two children. No node is allowed to have exactly one. Either both kids show up to the party or neither does.

That single constraint has real consequences. The number of leaves is always exactly one more than the number of internal nodes. Valid node counts are always odd. Segment trees, expression trees, and Huffman trees are all full binary trees in disguise. Pin down the definition and you'll solve a handful of interview problems faster and explain your reasoning without the uncomfortable pause.

The Rule: Zero Children or Two, Never One

Here is a full binary tree:

        1
       / \
      2   3
     / \
    4   5

Node 1 has two children. Node 2 has two children. Nodes 3, 4, and 5 have zero children. Every node obeys the rule.

Here is a tree that is NOT full:

        1
       / \
      2   3
     /
    4

Node 2 has exactly one child. That breaks the rule. Invalid. Rejected. No hire.

"Full" says nothing about whether the leaves are at the same depth or whether the tree is balanced. It's purely about child counts. A full binary tree can be wildly lopsided.

Full vs. Complete vs. Perfect: Three Words, Three Different Things

These three cause the most confusion. They sound interchangeable. They are not.

Type	What it requires
Full	Every node has 0 or 2 children
Complete	All levels filled except possibly the last, which fills left to right
Perfect	All internal nodes have 2 children AND all leaves are at the same depth

A perfect binary tree is always full and always complete. A full binary tree is not necessarily perfect or complete. A complete binary tree is not necessarily full, because a node on the last level can have just one child.

The interview trap is treating "full" and "complete" as synonyms. Heaps are stored as complete binary trees. Expression trees are full binary trees. Mixing them up leads to wrong claims about structure and wrong complexity analysis. The interviewer will make a note.

The Leaf Count Invariant

If a full binary tree has I internal nodes, it has exactly I + 1 leaf nodes. Total nodes: 2I + 1.

The proof is a single edge-counting argument. A tree with n nodes has n - 1 edges. In a full binary tree, each internal node contributes exactly two edges downward. So 2I = n - 1, giving n = 2I + 1. Since n = I + L, substituting gives L = I + 1.

This is a fast sanity check in interviews. If a problem describes a full binary tree with an even number of nodes, something is wrong. You know immediately, before touching any code.

Height: Don't Assume Short

A full binary tree with n nodes can have height anywhere from O(log n) to O(n).

The minimum is a perfectly balanced full tree: height floor(log2((n+1)/2)), which is O(log n).

The maximum is a "caterpillar" tree where every internal node has one leaf child and one internal-node child:

      1
     / \
    2   leaf
   / \
  3   leaf
 / \
4   leaf
...

With I internal nodes this gives height I, and since n = 2I + 1, height is O(n).

For any DFS traversal, the call stack can be O(log n) in the best case and O(n) in the worst. Don't assume a full binary tree is shallow just because it's called "full." The name is about width, not height.

Expression Trees: What You've Already Been Using

The most common full binary tree in production code is an expression tree (also called an abstract syntax tree for arithmetic). Every operator node has exactly two operands. Every operand is a leaf. The structure is full by definition.

The expression (3 + 4) * (2 - 1) maps to this tree:

Every internal node is an operator with two children. Every leaf is a number. Evaluating it is a postorder traversal: recurse left, recurse right, apply the operator. When you see a recursive evaluate(node) function in an interview, you're almost certainly working with a full binary tree. This structure shows up in compilers, calculators, query planners, and rule engines.

Recursion Is Cleaner on Full Trees

Because every non-leaf node has exactly two children, recursive algorithms have a clean base case: if the node has no children, it's a leaf.

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

You never need to guard against node.left is None and node.right is not None. On a valid full binary tree, either both children exist or neither does. That eliminates the half-null edge case that causes off-by-one bugs in general tree traversals. One less thing to get wrong at 11pm before an interview.

Checking Whether a Tree Is Full

Straightforward DFS. For every node, verify the number of non-null children is zero or two, never one.

def is_full_binary_tree(node):
    if node is None:
        return True
    left_exists = node.left is not None
    right_exists = node.right is not None
    if left_exists != right_exists:
        return False
    return is_full_binary_tree(node.left) and is_full_binary_tree(node.right)

Time: O(n). Space: O(h), where h ranges from O(log n) to O(n).

LeetCode 894: All Possible Full Binary Trees

LeetCode 894 asks you to generate all structurally unique full binary trees with exactly n nodes.

Since n = 2I + 1, a full binary tree can only have an odd number of nodes. If n is even, return an empty list. That check eliminates half the input space and makes you look like you know exactly what you're doing.

For odd n, split n - 1 nodes between the left and right subtrees. Each split must give both subtrees an odd count. Memoize to avoid recomputing the same subtree sizes:

from functools import lru_cache
from typing import Optional, List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def allPossibleFBT(n: int) -> List[Optional[TreeNode]]:
    if n % 2 == 0:
        return []
    if n == 1:
        return [TreeNode(0)]

    result = []
    for left_count in range(1, n - 1, 2):
        right_count = n - 1 - left_count
        for left in allPossibleFBT(left_count):
            for right in allPossibleFBT(right_count):
                root = TreeNode(0)
                root.left = left
                root.right = right
                result.append(root)
    return result

The number of distinct structures equals the Catalan number C((n-1)/2). The sequence: 1, 1, 2, 5, 14, 42. It grows fast, which is why memoization matters.

Every time you sit down to practice the night before your interview.

Complexity at a Glance

Operation	Time	Space (call stack)
Check if full	O(n)	O(h)
Count leaves	O(n)	O(h)
Height	O(n)	O(h)
Generate all full trees of size n	O(n · Catalan(n/2))	O(n · Catalan(n/2))

h ranges from O(log n) for balanced to O(n) for skewed. For skewed full trees, consider iterative DFS to avoid stack overflow.

Where Full Binary Trees Show Up in Interviews

Segment trees. A segment tree is always a full binary tree. Each internal node represents a range that splits into exactly two child ranges. You've probably implemented one without thinking of it this way.

Huffman trees. Huffman encoding builds a full binary tree where leaves are symbols and internal nodes hold merged frequencies. The full structure is a required invariant of the algorithm, not an accident.

Expression evaluation. Any problem where internal nodes are operators and leaves are values is a full binary tree problem. See binary tree interview problem patterns for a full list of what to expect. The clean two-children structure means your evaluator never needs to handle the half-null case.

Technical interview: "implement a segment tree." First week on the job: why is this JSON nested six levels deep.

If you want to practice explaining tree problems out loud under real interview conditions, SpaceComplexity runs voice-based mock interviews with rubric-based feedback. Tree problems are where most candidates lose points on communication, not code.

Make sure you have a crisp answer to "what is the difference between full and complete?" It comes up in the first five minutes.

Further Reading

• Binary Tree (Wikipedia): formal definitions of full, complete, perfect, and balanced binary trees in one place
• LeetCode 894: All Possible Full Binary Trees: the primary interview problem on this structure
• Catalan Numbers (Wikipedia): the combinatorial sequence that counts structurally distinct full binary trees
• Expression Tree (GeeksforGeeks): the canonical real-world application of full binary trees
• Segment Tree (GeeksforGeeks): a widely tested interview structure that is always a full binary tree