Binary Tree

A binary tree is a hierarchical data structure in which every node has at most two children, conventionally distinguished as the left child and the right child. It is the substrate underneath nearly every other tree-flavored data structure used in interviews — Binary Search Tree, Binary Heap, AVL Tree, Red-Black Tree, expression trees, syntax trees, segment trees, etc. — and the recursion patterns that work on it generalize to all of them. This note covers the terminology, the structural taxonomy (full vs complete vs perfect vs balanced vs degenerate), the foundational counting identities (max nodes at depth d = 2^d, max nodes in tree of height h = 2^(h+1) - 1), the array-indexing trick that lets a complete binary tree be stored without pointers, and the canonical recursive shape that solves almost every binary-tree problem.

1. Intuition — A Choose-Your-Own-Adventure Book

A binary tree is the data-structure analogue of a choose-your-own-adventure book. Every page (node) contains some content (the node’s value) plus a question with two possible choices: “to do X, turn to page L; to do Y, turn to page R.” Some pages have only one choice (“you may only proceed to page L”) and some are endings (no choices — these are the leaves). The first page you start on is the root.

The shape of the book — how deep it goes, how wide it gets, how lopsided it is — drives both the capacity of stories the book can encode and the worst-case time it takes to navigate from the root to any specific page. A shallow, evenly-fanned book lets you reach any ending in ≈ log₂ n page-flips; a single long chain of “always turn to L” pages is n flips deep and effectively a linked list in disguise. This shape-vs-cost trade-off is the through-line of every later note in the trees batch.

2. Terminology — Speaking the Language

Tree problems live or die on precise vocabulary, and interviewers will quietly judge sloppy use of “depth” vs “height” or “complete” vs “full.” The terms below are the ones used by CLRS Ch. B.5 and by every subsequent note in this batch.

• Node. A unit of the tree holding a value plus references (pointers) to its children. The empty tree is null / None.
• Edge. The pointer from a parent to one of its children. A tree of n nodes has exactly n − 1 edges (every non-root node is the target of exactly one edge from its parent).
• Root. The unique node with no parent — the entry point.
• Parent / Child. If node p has an edge to node c, then p is the parent of c and c is a child of p. Each node has at most one parent (except the root, which has none).
• Siblings. Two nodes that share the same parent.
• Leaf (a.k.a. external / terminal node). A node with zero children. In some texts the null slots themselves are called external nodes, and the value-bearing nodes are internal; this note uses the more common “leaf = childless node” convention.
• Internal node. Any non-leaf node (i.e., a node with at least one child).
• Ancestor / Descendant. a is an ancestor of d if a lies on the unique path from the root to d. Conversely, d is then a descendant of a. Every node is its own ancestor and its own descendant by convention (you’ll see “proper ancestor” used to exclude the node itself).
• Subtree rooted at v. The node v together with all of its descendants and the edges among them. Subtrees are themselves binary trees, which is what makes recursion natural.
• Depth of a node. The number of edges on the path from the root down to that node. The root has depth 0.
• Level. A common synonym for depth. “Level 0” = the root. Some books index levels starting at 1; CLRS uses 0. Be consistent within one note and clarify if it matters.
• Height of a node. The number of edges on the longest path from that node down to a leaf in its subtree. A leaf has height 0. The empty tree’s height is conventionally −1 (so that height(non-empty) = 1 + max(height(left), height(right)) works out cleanly).
• Height of the tree. The height of its root. A single-node tree has height 0; an empty tree has height −1.
• Path length. The number of edges (or sometimes the number of nodes; specify which) along a sequence of parent-child links.

"Depth" and "height" measured in edges vs nodes

Different textbooks count depth/height as either edges or nodes. CLRS counts edges (root depth 0, single-node tree height 0). Some competitive-programming sources count nodes (root depth 1, single-node tree height 1). Both conventions are valid; pick one and be consistent. Throughout this batch (and in the formulas below) we use edges — the CLRS convention.

3. The Structural Taxonomy — Full, Complete, Perfect, Balanced, Degenerate

These five adjectives get conflated constantly in interviews. They are not synonyms, and getting them right matters because algorithms and complexity guarantees depend on the precise shape.

3.1 Full (a.k.a. proper / strict)

A binary tree is full if every internal node has exactly two children — never one. Leaves of course still have zero. So in a full tree, every node has either 0 or 2 children, never 1.

        1
       / \
      2   3      ← full: every internal node has exactly 2 children
     / \
    4   5

Note: a full binary tree need not be balanced or complete. Useful identity: a full binary tree with L leaves has exactly L − 1 internal nodes, hence 2L − 1 nodes total. Proof sketch: each internal node contributes 2 children; total child-slots = 2 × (internal count); each non-root node fills one slot, so 2I = (n − 1), hence I = (n − 1)/2, hence L = n − I = (n + 1)/2. Rearranging: n = 2L − 1, I = L − 1. This identity drops out of expression-tree problems frequently.

3.2 Complete

A binary tree is complete if every level except possibly the last is completely filled, and on the last level all nodes are pushed as far left as possible. Picture pouring the tree’s nodes in level by level, left to right; you stop only when you run out of nodes, and you never skip a slot.

        1
       / \
      2   3
     / \  /
    4  5 6        ← complete: last level filled left-to-right

The “no gaps” property is exactly what makes complete binary trees representable as a contiguous array (§4) and is the structural invariant of the binary heap.

3.3 Perfect

A binary tree is perfect if every internal node has exactly two children and every leaf is at the same depth. So a perfect tree is full and complete and every level is fully populated. It has exactly 2^(h+1) − 1 nodes for height h.

        1
       / \
      2   3
     / \ / \
    4  5 6  7    ← perfect: every level fully populated

Every perfect binary tree is complete and full. Most complete trees are not perfect (the last level may be partial). Most full trees are not complete (the leaves can be at different depths).

3.4 Balanced (height-balanced)

There are several non-equivalent definitions in circulation. The most common one (used by LeetCode 110 and most algorithm textbooks): a binary tree is height-balanced if for every node, the heights of its left and right subtrees differ by at most 1. This is the AVL invariant.

A weaker version says a tree is balanced if height = O(log n) — a structural rather than per-node guarantee. Red-black trees are balanced in this weaker sense (height ≤ 2 log₂(n+1)) without satisfying the strict per-node AVL criterion.

The takeaway: “balanced” without qualification usually means the AVL-style per-node criterion, but always confirm the definition the interviewer has in mind.

3.5 Degenerate (skewed / pathological)

A degenerate binary tree is one in which every internal node has only one child. It is structurally a linked list — height = n − 1, depth-to-leaf operations cost O(n). This is the worst-case shape for an unbalanced Binary Search Tree receiving sorted inserts and is the case that motivates self-balancing trees.

1
 \
  2
   \
    3
     \
      4    ← right-skewed degenerate tree

4. Array Representation of Complete Binary Trees

A complete binary tree (and by extension a perfect one) can be stored in a single contiguous array with no pointers — the parent/child relationships are derived from index arithmetic. This is exactly how a Binary Heap stores its nodes.

Two indexing conventions exist; both appear in textbooks. Pick one and never mix.

0-indexed (Python / C / common modern choice):

• The root sits at index 0.
• For a node at index i:
  • Left child: 2*i + 1
  • Right child: 2*i + 2
  • Parent: (i − 1) // 2 (integer division; undefined for i = 0)

1-indexed (CLRS, classical heap presentations):

• The root sits at index 1. Index 0 is unused (or used as a sentinel).
• For a node at index i:
  • Left child: 2*i
  • Right child: 2*i + 1
  • Parent: i // 2

The 1-indexed math is cleaner (no +1s to remember), which is why CLRS prefers it. The 0-indexed math fits naturally with Python lists.

Why this works only for complete trees. The mapping assumes node k exists iff k < n for an n-node tree. If the tree has gaps (missing children at intermediate levels), the array has “holes” — slots reserved for non-existent nodes — which (a) wastes memory and (b) breaks the bijection that lets parent and child indices be computed in O(1). A general (non-complete) binary tree can be stored in an array with explicit null markers for missing children, but for a deep sparse tree this can blow up to O(2^h) slots even though n is small.

Worked example — heapifying [3, 1, 4, 1, 5, 9, 2, 6] (0-indexed):

Index:  0  1  2  3  4  5  6  7
Value:  3  1  4  1  5  9  2  6

Visualized as a tree:
                3            ← index 0 (root)
              /   \
             1     4         ← indices 1, 2
            / \   / \
           1   5 9   2       ← indices 3, 4, 5, 6
          /
         6                   ← index 7

Index 1’s children should be at 2*1 + 1 = 3 and 2*1 + 2 = 4 — values 1 and 5. ✓ Index 7’s parent should be at (7 − 1) // 2 = 3 — value 1. ✓

5. Counting Identities (the “How Many Nodes?” Math)

These identities show up in worst-case-complexity arguments throughout the tree notes.

5.1 Maximum nodes at depth d

A binary tree has at most 2^d nodes at depth d.

Proof by induction on d: at depth 0 there is 1 root, and 2^0 = 1. Assume there are at most 2^(d−1) nodes at depth d − 1; each of them contributes at most 2 children at depth d, so depth d has at most 2 × 2^(d−1) = 2^d nodes. ∎

This bound is tight for perfect binary trees: every level is filled exactly to capacity.

5.2 Maximum total nodes in a tree of height h

A binary tree of height h has at most 2^(h+1) − 1 nodes.

Proof: sum the per-depth maxima from depth 0 to depth h:

1 + 2 + 4 + ... + 2^h = Σ_{d=0}^{h} 2^d = 2^(h+1) − 1

(geometric series). ∎

This is exactly the number of nodes in a perfect binary tree of height h.

5.3 Minimum height of an n-node tree

If a tree has n nodes and height h, then by §5.2 we have n ≤ 2^(h+1) − 1. Solving for h:

2^(h+1) ≥ n + 1
h + 1   ≥ log₂(n + 1)
h       ≥ ⌈log₂(n + 1)⌉ − 1   =   ⌊log₂ n⌋    (for n ≥ 1)

So the minimum possible height is ⌊log₂ n⌋, achieved when the tree is as “bushy” as possible. The maximum possible height is n − 1, achieved when the tree is degenerate (a chain).

This Θ(log n) lower bound on height is the entire reason self-balancing tree algorithms exist: they enforce h = O(log n) so that operations like search, insert, and delete (which all cost O(h)) cost O(log n).

5.4 Number of binary trees with n nodes

The count of distinct binary tree shapes on n nodes is the n-th Catalan number:

C_n  =  (1 / (n + 1)) · C(2n, n)

where C(2n, n) is the binomial coefficient. For n = 1, 2, 3, 4, 5 we get 1, 2, 5, 14, 42. This grows roughly as 4^n / n^(3/2) — very fast. Useful for combinatorial proofs and for problems like LC 96 (Unique Binary Search Trees).

6. Recursion Patterns — The Universal Template

The vast majority of binary-tree algorithms fit this single recursive shape:

solve(node):
    if node is null:        # base case
        return identity_for_empty_subtree
    left_result  = solve(node.left)
    right_result = solve(node.right)
    return combine(node.value, left_result, right_result)

This is the post-order template (children processed first, then current node). It computes any aggregate that depends on a node’s two subtrees, including:

• height(node) = 1 + max(height(left), height(right)) for non-empty; −1 for empty.
• size(node) = 1 + size(left) + size(right) for non-empty; 0 for empty.
• sum(node) = node.val + sum(left) + sum(right).
• max_in(node) = max(node.val, max_in(left), max_in(right)).
• is_balanced, is_symmetric, tree_diameter, max_path_sum, lca — all post-order patterns.

A small variant — pre-order — does work before descending:

solve(node, accumulator):
    if node is null: return
    accumulator = combine(accumulator, node.value)
    solve(node.left,  accumulator)
    solve(node.right, accumulator)

This pattern shows up when the result depends on the path from root to current node (e.g., LC 112 Path Sum, LC 124 max path sum from root).

Once you internalize these two templates (post-order combines child results; pre-order threads state down), the bulk of binary-tree LeetCode falls into a few dozen variations.

7. Python Implementation

The Node class used throughout this batch and consistent with Tree Traversals:

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

Building the example tree from §2 in code:

#         1
#        / \
#       2   3
#      / \   \
#     4   5   6
 
root = Node(1,
            left=Node(2, left=Node(4), right=Node(5)),
            right=Node(3, right=Node(6)))

Computing standard tree statistics with the post-order template:

def height(node):
    """Height in edges; empty tree → -1, single node → 0."""
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))
 
def size(node):
    """Number of nodes in the subtree."""
    if node is None:
        return 0
    return 1 + size(node.left) + size(node.right)
 
def is_balanced(node):
    """AVL-style: every node's two subtree heights differ by at most 1."""
    def check(n):
        # Returns (balanced?, height). Short-circuits on imbalance.
        if n is None:
            return True, -1
        lb, lh = check(n.left)
        if not lb: return False, 0
        rb, rh = check(n.right)
        if not rb: return False, 0
        return abs(lh - rh) <= 1, 1 + max(lh, rh)
    return check(node)[0]

The is_balanced implementation is worth dwelling on: a naive version would call height from inside an outer is_balanced recursion, costing O(n²) (each node’s height is recomputed once per ancestor). The fused version above returns both the balance flag and the height in a single post-order pass, achieving O(n). This “compute multiple things in one traversal by returning a tuple” trick recurs throughout the batch (Tree Diameter, Lowest Common Ancestor all use it).

8. Complexity (Generic Operations)

Operation	Time	Space
Single full traversal (any of pre/in/post/level — see Tree Traversals)	Θ(n)	Θ(h) (recursion / stack) for DFS; Θ(w) (max width) for BFS
height, size, sum, max (single post-order pass)	Θ(n)	Θ(h)
Search for a value (no ordering invariant)	O(n)	O(h)
Insert (location-specified)	O(1) after pointer updates	O(1)
Insert (find first empty spot, e.g. by level-order BFS)	O(n)	O(w)
is_balanced (fused post-order)	Θ(n)	Θ(h)

For balanced trees, h = Θ(log n), so every O(h)-bounded operation is Θ(log n). For degenerate trees, h = Θ(n) and the same operations cost Θ(n).

The Θ(n) lower bound on full traversal is unavoidable: by definition you must visit every node at least once.

9. Variants and Specializations

The general “binary tree” idea specializes into a small zoo of related structures, each with its own note:

• Binary Search Tree — adds the BST invariant left < node < right, enabling O(h) search/insert/delete.
• Binary Heap — a complete binary tree with the heap-order invariant; backs priority queues. Stored as an array using §4’s index math.
• AVL Tree (planned, gray) — a self-balancing BST that maintains |height(left) − height(right)| ≤ 1 at every node via rotations.
• Red-Black Tree (planned, gray) — a self-balancing BST with weaker per-node guarantees but excellent practical performance; used in C++ std::map, Java’s TreeMap, and the Linux kernel’s rbtree.
• Expression / syntax trees — internal nodes are operators, leaves are operands; in-order traversal recovers infix expression, post-order gives RPN.
• Tries (a.k.a. prefix trees) — not binary in general; one child per alphabet symbol. But the binary trie is a binary-tree variant where left = “next bit is 0” and right = “next bit is 1,” used for IP routing tables and binary representations of strings.
• Segment trees / Fenwick trees — complete or near-complete binary trees representing intervals; back fast range-query data structures.
• K-d trees — binary trees that partition k-dimensional space, alternating which coordinate they split on at each level.

The list goes on. The point is that the structural definition of “binary tree” is generic; specific invariants layered on top yield wildly different functionality.

10. Pitfalls

10.1 Confusing “complete” with “full”

This is the classic mix-up. Full = every internal node has 0 or 2 children (no “only-child” nodes). Complete = every level is filled left-to-right with no gaps. A tree can be full but not complete (e.g., a balanced full tree where the rightmost leaf is missing — wait, that wouldn’t be full either; better example: a bushy tree of mixed depths where every non-leaf has 2 children but levels aren’t all filled), or complete but not full (a complete tree’s last level is filled left-to-right but may stop mid-level, so the rightmost internal node may have only a left child). The diagrams in §3.1 and §3.2 show distinct shapes; trace through and convince yourself.

10.2 Off-by-one in “height” definitions

If you switch between the “height = number of edges” and “height = number of nodes” conventions mid-derivation, formulas like h ≥ log₂(n + 1) − 1 become h ≥ log₂(n + 1) and your complexity analysis is off by 1 everywhere. Pick one convention and stick to it for the entire problem.

10.3 Empty tree edge case

null / None is a valid binary tree (the empty tree). Most recursive functions need an explicit base case for it. Forgetting this is the single most common cause of AttributeError: 'NoneType' object has no attribute 'left' in tree code.

10.4 The O(n²) height bug

Computing height(node) from inside a function that recurses on every node turns an intended O(n) algorithm into O(n²) for skewed trees (each node’s height call traverses its whole subtree). Fix: compute height as part of the same post-order pass that needs it (return tuples; see §7’s is_balanced).

10.5 Mutating a tree while traversing

Modifying node.left or node.right mid-traversal corrupts the recursion’s view of the structure. If you must mutate, either (a) collect the planned changes during a read-only pass and apply them in a second pass, or (b) carefully reason about post-order mutation (delete children before processing the parent — safe).

10.6 Treating “binary tree” as implying “BST”

A general binary tree has no ordering invariant. You cannot binary-search inside it; you cannot do an in-order traversal and expect sorted output. Many bugs come from someone reading “binary tree” in a problem statement and silently assuming “binary search tree.” Re-read the prompt before optimizing.

10.7 Array indexing for non-complete trees

The 2i+1 / 2i+2 index math in §4 only works correctly for complete binary trees, where there are no missing slots in the middle. Storing a sparse tree in an array using these indices either wastes massive memory or produces incorrect parent/child links. If the tree is sparse, use pointer-based representation, not array-based.

11. Diagram — A Single Tree, All Five Adjectives at Once

flowchart TD
    R((1)) --> L((2))
    R --> RR((3))
    L --> LL((4))
    L --> LR((5))
    RR --> RL((6))
    RR --> RRR((7))
    LL --> LLL((8))
    LL --> LLR((9))

What this diagram shows. This is a perfect binary tree of height 3: every internal node has exactly two children (so it’s full), every level is fully populated left-to-right (so it’s complete), and every leaf sits at the same depth (so it’s perfect). It has 2^4 − 1 = 15 nodes’ worth of capacity at depth ≤ 3, but we’ve drawn only the 9 of them needed to demonstrate the shape — extending to a full 15 nodes would require adding two children under each of nodes 5, 6, 7. The root (node 1) has depth 0 and height 3. Node 8 has depth 3 and height 0. The tree is also vacuously height-balanced (every node’s subtree heights differ by at most 1, in fact by exactly 0). And it is not degenerate — degenerate would mean a single chain, the polar opposite of this shape.

12. Common Interview Problems

LC #	Problem	Pattern / Note
104	Maximum Depth of Binary Tree	Post-order; height computation
110	Balanced Binary Tree	Fused post-order returning (balanced, height)
100	Same Tree	Parallel pre-order on two trees
101	Symmetric Tree	Mirror-recursion on left/right of root
222	Count Complete Tree Nodes	Exploit completeness for O(log² n)
226	Invert Binary Tree	Post-order swap
199	Binary Tree Right Side View	Level-order; emit last node per level
543	Diameter of Binary Tree	See Tree Diameter
124	Binary Tree Maximum Path Sum	Post-order with global update
297	Serialize / Deserialize	See Serialize and Deserialize Binary Tree
236	Lowest Common Ancestor	See Lowest Common Ancestor
105 / 106	Construct from preorder + inorder / inorder + postorder	See Tree Traversals
96	Unique Binary Search Trees	Catalan number application

13. Open Questions

• When does the array-encoded complete-binary-tree representation beat a pointer-based one in practice? Heaps and segment trees clearly do. For other complete-tree workloads it depends on cache behavior and update patterns.
• Is there a unifying language for “full + complete + perfect + balanced + degenerate” that doesn’t require five overlapping definitions? The literature has not converged.
• Why do Catalan numbers appear in both “number of binary tree shapes on n nodes” and “number of valid parenthesizations of n pairs”? They count the same set of recursive structures up to bijection, but the deeper combinatorial reason is worth its own note.

14. See Also

• Tree Traversals — pre/in/post/level order, the four canonical visit sequences
• Binary Search Tree — adds an ordering invariant to gain O(h) search
• Binary Heap — a complete binary tree backing a priority queue
• Tree Diameter — a canonical post-order computation on any binary tree
• Lowest Common Ancestor — multiple algorithms, all built on binary-tree recursion
• Serialize and Deserialize Binary Tree — encoding/decoding an arbitrary binary tree
• Depth-First Search — graph generalization of pre/in/post-order
• Breadth-First Search — graph generalization of level-order
• AVL Tree (planned) — self-balancing BST
• Red-Black Tree (planned) — self-balancing BST
• Big-O Notation
• SWE Interview Preparation MOC