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

Converting Between Representations

Implement algorithms to convert binary trees from node-based to array representation and vice versa.

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:

  1. Size the array: Calculate the maximum index you'll need based on tree height
  2. Level-order traversal: Visit nodes level by level (use a queue)
  3. Place at correct index: For each node at position i, store its value at array[i]
  4. Mark null children: When a node is missing, store a sentinel value (like null or -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:

  1. Start at root: Create the root node from array[0]
  2. Apply index formulas: For node at index i, its left child is at 2i+1, right at 2i+2
  3. Skip sentinel values: If array[index] is null/sentinel, don't create that child
  4. 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.