How is a binary tree stored with linked nodes, and how does it differ from a general tree's nodes?
Each node stores four references: its element, its parent, its left child and its right child. The general tree's sequence of children is replaced by exactly two fixed fields.
* Solid arrows point down to the children, dashed ones back up to the parent; ∅ marks a missing child. *
Since a binary node has at most two children, and they must be distinguishable as left and right, a list is unnecessary. Two fields do the job:
| Field | Points to |
|---|---|
| element | the stored data |
| parent | the parent (null at the root) |
| left | the left child (null if absent) |
| right | the right child (null if absent) |
This makes left(p), right(p) and parent(p) single field reads, $O(1)$, and it uses exactly as much memory as there are nodes. A missing child is simply a null reference, so an unbalanced tree wastes nothing, which is the key advantage over the array-based layout.