Converting Between Representations
You'll learn how to transform a binary tree from node-based form into array form and back again.
The Core Challenge
Binary trees can exist in two formats: node-based (using pointers/references) and array-based (using index formulas). Sometimes you need to convert between them—perhaps to serialize a tree for storage, switch to a more cache-friendly format, or interface with different systems.
Node-to-Array Conversion
To convert a node-based tree to an array:
- Size the array: Calculate the maximum index you'll need based on tree height
- Level-order traversal: Visit nodes level by level (use a queue)
- Place at correct index: For each node at position
i, store its value atarray[i] - Mark null children: When a node is missing, store a sentinel value (like
nullor-1)
Key insight: You're mapping the tree's logical structure (which index would this node occupy?) onto array positions, even if the tree isn't complete.
Array-to-Node Conversion
To convert an array back to nodes:
- Start at root: Create the root node from
array[0] - Apply index formulas: For node at index
i, its left child is at2i+1, right at2i+2 - Skip sentinel values: If
array[index]is null/sentinel, don't create that child - Recursively build: Process each valid index, creating nodes and linking them
Analogy: Think of it like converting between a family tree poster (visual/node-based) and a numbered list in a genealogy book (array-based). You need rules to know where each person belongs in each format.
Key Takeaway: Converting between tree representations requires systematically mapping between pointer relationships and array index formulas, handling missing nodes with sentinels to preserve structure.