Part 9 — Binary Trees

Binary trees are one of the most important data structures in coding interviews. They are useful for representing hierarchical information and form the foundation for structures and algorithms such as binary search trees, heaps, expression trees, and hierarchical models.

The goal of this part is not to memorize individual tree problems. Instead, we will develop a reusable way to reason about tree structure, choose a traversal, maintain state, eliminate repeated work, and analyze complexity.

The Binary Trees section of Elements of Programming Interviews in Python covers topics including height balance, symmetry, lowest common ancestors, traversal-based reconstruction, path problems, tree exterior, and level-next relationships. citeturn0search0turn0search1

1. Understanding a Binary Tree

A binary tree is either empty or consists of a root, a left subtree, and a right subtree. Each subtree is itself a binary tree.

class BinaryTreeNode:
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

Example:

          A
        /   \
       B     C
      / \   / \
     D   E F   G

A is the root, B and C are children of A, and D, E, F, and G are leaves.

2. Depth and Height

The depth of a node is its distance from the root. The height of a tree is determined by its deepest node. Always clarify the exact height convention when an interview problem depends on it.

Many tree algorithms have complexity expressed using the tree height h:

O(h)

For a balanced tree, h is typically O(log n). For a skewed tree, h can be O(n).

That distinction is critical in complexity analysis.

3. Important Binary-Tree Shapes

Full Binary Tree

Every non-leaf node has exactly two children.

Perfect Binary Tree

Every internal node has two children and all leaves are at the same depth.

Complete Binary Tree

Every level is filled except possibly the last, and nodes on the last level are as far left as possible.

Skewed Tree

A tree can become almost linear when nodes repeatedly have only one child. This is why O(h) should not automatically be interpreted as O(log n).

4. The Three Fundamental Traversals

Inorder

Left → Root → Right

def inorder(root):
    if root is None:
        return
    inorder(root.left)
    print(root.data)
    inorder(root.right)

In a binary search tree, inorder traversal visits keys in sorted order.

Preorder

Root → Left → Right

def preorder(root):
    if root is None:
        return
    print(root.data)
    preorder(root.left)
    preorder(root.right)

Postorder

Left → Right → Root

def postorder(root):
    if root is None:
        return
    postorder(root.left)
    postorder(root.right)
    print(root.data)

A useful interview rule is:

Need the root first? Think preorder.
Need children before the parent? Think postorder.
Need sorted ordering from a BST? Think inorder.
Need level-by-level processing? Think BFS.

5. Why Recursion Fits Trees

Binary trees are recursively defined, so many algorithms naturally follow this pattern:

Solve left subtree
        ↓
Solve right subtree
        ↓
Combine the results

The powerful part is that a recursive call can return more information than just a single value. For example, a subtree can return both:

(balance status, height)

This lets a parent solve several related questions during one traversal.

6. Testing Whether a Tree Is Height-Balanced

A height-balanced tree is one where the heights of the left and right subtrees of every node differ by at most one.

A naive solution may repeatedly calculate subtree heights. A better solution performs a bottom-up traversal and returns both balance information and height.

def is_balanced(root):
    def check(node):
        if node is None:
            return True, -1

        left_balanced, left_height = check(node.left)
        if not left_balanced:
            return False, 0

        right_balanced, right_height = check(node.right)
        if not right_balanced:
            return False, 0

        balanced = abs(left_height - right_height) <= 1
        height = max(left_height, right_height) + 1
        return balanced, height

    return check(root)[0]

Complexity: O(n) time and O(h) auxiliary space.

The reusable pattern is:

Return enough information from a child so the parent does not need to recompute it.

7. Testing Whether a Tree Is Symmetric

A tree is symmetric when its left and right subtrees are mirror images.

          A
        /   \
       B     B
      / \   / \
     C   D D   C

The recursive comparison is:

def is_symmetric(root):
    def mirror(left, right):
        if left is None and right is None:
            return True
        if left is None or right is None:
            return False

        return (
            left.data == right.data
            and mirror(left.left, right.right)
            and mirror(left.right, right.left)
        )

    return root is None or mirror(root.left, root.right)

The invariant is that the two nodes being compared always represent corresponding positions in the two mirrored subtrees.

Complexity: O(n) time and O(h) space.

8. Lowest Common Ancestor

The Lowest Common Ancestor (LCA) of two nodes is the deepest node that is an ancestor of both.

          A
        /   \
       B     C
      / \   / \
     D   E F   G

The LCA of D and E is B. The LCA of D and F is A.

For a general binary tree without parent pointers, a recursive solution can search the left and right subtrees and propagate the required information upward. The important optimization is to avoid repeatedly searching the same subtree.

Typical complexity is:

Time:  O(n)
Space: O(h)

LCA With Parent Pointers

If each node has a parent pointer, first determine the depths of the two nodes. Move the deeper node upward until both nodes are at the same depth, then move both upward together until they meet.

Time:  O(h)
Space: O(1)

This illustrates a general principle: additional metadata can reduce both computation and auxiliary memory.

9. Root-to-Leaf Path Problems

Many tree problems carry state from the root toward the leaves.

For a path-sum problem, instead of constructing the path repeatedly, maintain the remaining target:

def has_path_sum(root, target):
    if root is None:
        return False

    if root.left is None and root.right is None:
        return target == root.data

    remaining = target - root.data

    return (
        has_path_sum(root.left, remaining)
        or has_path_sum(root.right, remaining)
    )

The broader pattern is:

Parent state
     ↓
Child
     ↓
Updated state

This applies to path sums, path constraints, accumulated values, and many other tree problems.

10. Iterative Traversal

When recursion is not allowed, simulate the call stack explicitly.

Iterative Inorder

def inorder_iterative(root):
    stack = []
    result = []
    current = root

    while stack or current:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        result.append(current.data)
        current = current.right

    return result

Iterative Preorder

def preorder_iterative(root):
    if root is None:
        return []

    stack = [root]
    result = []

    while stack:
        node = stack.pop()
        result.append(node.data)

        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

The right child is pushed first because a stack is LIFO, so the left child is processed first.

Complexity: O(n) time and O(h) auxiliary space.

11. Reconstructing a Tree From Traversals

Suppose preorder and inorder traversals are available.

The first element of preorder identifies the root. Finding that root in inorder divides the sequence into the left and right subtrees.

Preorder → identify root
             ↓
Inorder → split left/right
             ↓
Recursively reconstruct

To avoid repeatedly scanning the inorder sequence, precompute an index map:

positions = {
    value: index
    for index, value in enumerate(inorder)
}

Then root-position lookup is expected O(1).

The overall reconstruction can be performed in O(n) time with O(n) additional storage for the index structure and recursion-related state.

This demonstrates an important optimization pattern:

Repeated search
      ↓
Precompute index
      ↓
Fast lookup
      ↓
Linear overall processing

12. Leaf Extraction and Tree Exterior

A leaf has no children:

node.left is None and node.right is None

A left-to-right DFS naturally visits leaves in left-to-right order.

The exterior of a tree can be reasoned about as:

Root
 ↓
Left boundary
 ↓
Leaves from left to right
 ↓
Right boundary in reverse

The key implementation challenge is avoiding duplicates, especially when boundary nodes are also leaves.

13. Level-Next Relationships

Some tree representations include an additional pointer such as:

node.next

which points to another node on the same level.

For a perfect tree:

          A
        /   \
       B     C
      / \   / \
     D   E F   G

we want relationships such as:

B.next = C
D.next = E
E.next = F
F.next = G

If the structure provides enough information, these links can sometimes be created without maintaining a full queue. This is another example of using the data structure itself to reduce auxiliary memory.

14. Complexity: Always Think About Height

For a tree containing n nodes:

A full traversal is generally O(n) because every node may need to be visited.
A path-based operation can be O(h).
Recursive DFS typically uses O(h) call-stack space.

For a balanced tree:

h = O(log n)

For a skewed tree:

h = O(n)

Therefore, a Staff-level candidate should always distinguish between n and h when discussing tree complexity.

15. Common Interview Mistakes

Assuming every tree is balanced

A generic binary tree may be skewed.

Recomputing subtree information

If the same height, count, or property is recalculated repeatedly, look for a bottom-up solution that returns the information once.

Confusing a leaf with a node that has one missing child

A leaf has both children missing.

Ignoring parent pointers or other metadata

Existing structural information may eliminate an entire traversal or reduce memory requirements.

Choosing traversal by memorization

Instead, ask what information must be available before processing the current node.

16. The Reusable Binary-Tree Patterns

Pattern 1 — Bottom-Up Tree DP

Left subtree
      ↓
Right subtree
      ↓
Combine

Use when the parent depends on information computed by its children.

Examples include height, balance, and subtree properties.

Pattern 2 — Top-Down State Propagation

Parent state
     ↓
Child
     ↓
Updated state

Use for path sums, accumulated values, and path constraints.

Pattern 3 — Explicit Stack

Recursive call stack
        ↓
Explicit stack

Use when iterative DFS is required.

Pattern 4 — Structural Metadata

Useful metadata includes:

parent pointer
subtree size
level-next pointer
cached subtree properties

Metadata can reduce repeated work and improve query efficiency.

Pattern 5 — Precomputation

When an algorithm repeatedly searches for the same type of information, precompute an index or cache when the memory trade-off is worthwhile.

17. Staff-Level Mental Model

A beginner asks:

Which binary-tree problem is this?

A stronger engineer asks:

What information needs to flow through the tree?

Then reason through:

What does the parent need from its children?
             ↓
What should the recursive call return?
             ↓
Which traversal provides that information?
             ↓
Can repeated work be eliminated?
             ↓
Can existing metadata help?
             ↓
What is the worst-case height?
             ↓
What are the time and space trade-offs?

This is the transition from solving coding exercises to designing algorithms.

18. Interview Checklist

Before moving to the next part, you should be comfortable with:

Binary-tree representation
Depth and height
Full, perfect, complete, and skewed trees
Inorder traversal
Preorder traversal
Postorder traversal
Recursive DFS
Iterative DFS
Height-balanced trees
Symmetric trees
Lowest Common Ancestor
LCA with parent pointers
Root-to-leaf path problems
Path-sum problems
Tree reconstruction from traversal data
Leaf extraction
Tree exterior
Level-next relationships
Complexity in terms of n and h

19. Final Takeaway

The most important lesson from binary trees is not a particular implementation.

Use the structure of the tree to eliminate unnecessary work.

When facing a new tree problem, use this sequence:

Understand the structure
        ↓
Identify the required information
        ↓
Choose traversal order
        ↓
Define the recursive state
        ↓
Establish an invariant
        ↓
Eliminate repeated work
        ↓
Analyze O(n) vs O(h)
        ↓
Consider iterative or metadata-based alternatives

Once this mental model becomes natural, unfamiliar binary-tree problems stop looking like isolated puzzles. They become variations of a small set of reusable patterns.

Part 8 — Stacks & Queues
↓
Part 9 — Binary Trees
↓
Part 10 — Heaps

The next part moves from hierarchical traversal to priority-based processing and introduces heaps for top-k problems, merging sorted streams, and scheduling.