What You'll Learn
You'll learn the mathematical formulas used to navigate parent and child relationships in an array-based binary tree representation.
Why Index Formulas Matter
When you store a complete binary tree in an array (as introduced in the previous lesson), you need a way to find where a node's parent or children live in that flat array. Index formulas give you instant access without needing pointers or links.
The Three Essential Formulas
Assume you're looking at a node stored at array index i (where the root is at index 0):
Finding Children
- Left child is at index:
2i + 1 - Right child is at index:
2i + 2
Finding the Parent
- Parent is at index:
(i - 1) / 2(using integer division)
How It Works
Think of it like a family tree photo arranged in rows. The root is in row 0. Each subsequent row contains twice as many people. Given someone's position number, these formulas tell you exactly where their parent and children are positioned.
Example: If a node is at index 2:
- Left child:
2(2) + 1 = 5 - Right child:
2(2) + 2 = 6 - Parent:
(2 - 1) / 2 = 0(integer division)
This works because the array layout follows level-order: root, then all level-1 nodes, then all level-2 nodes, etc. The mathematical relationship between levels creates this predictable pattern.
These formulas only work reliably for complete binary trees where the array has no gaps, which is why complete trees are ideal for array representation.
Key Takeaway: In an array-based binary tree, use 2i+1 and 2i+2 to find children, and (i-1)/2 to find the parent of node at index i — enabling pointer-free tree navigation.