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).