Course contentsShow
← Computer Science
Lesson 466 of 2,87211. Binary TreesFree lesson

Representing Null Children

Handle missing children: null pointers in node structures vs unused indices or sentinel values in arrays.

Representing Null Children

You'll learn how different tree structures indicate when a node is missing a child.

The Problem of Missing Children

In binary trees, not every node has two children. A leaf has no children, and many internal nodes have only one. Your data structure needs a clear, unambiguous way to represent "there is no child here."

Node-Based Representation: Null Pointers

In a node structure with pointers, this is straightforward. Each node has left and right pointer fields. When a child doesn't exist, you simply set that pointer to null (or nullptr, None, depending on your language).

Node:
  data: 5
  left: null        ← explicitly shows no left child
  right: pointer to another node

The null pointer is self-documenting: "nothing here." Checking if (node.left == null) tells you immediately whether a left child exists.

Array-Based Representation: Unused Indices

In array-based complete binary trees, missing children create a challenge. You typically handle this in one of two ways:

Sentinel Values: Store a special value (like -1, null, or None) at array positions where nodes don't exist. This works, but wastes space if you have many missing nodes.

Sparse Storage: Only store actual nodes and track valid indices separately, though this complicates the simple parent-child index formulas you rely on (2i+1, 2i+2).

Why This Matters

The representation affects how you traverse the tree. With pointers, you check for null before following a link. With arrays, you check if an index is within bounds and whether that position contains valid data.

Key Takeaway: Null children are represented as null pointers in node structures (simple and clear) or as sentinel values/unused indices in arrays (more complex, especially for incomplete trees).