15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
The array representation stores the tree in level order, with the root at index 0. A node at index i has its left child at 2i + 1 and its right child at 2i + 2. Its parent is at floor((i - 1) / 2). Missing nodes keep a null slot, so positions never shift.
| Root | Index 0 |
|---|---|
| Left child of i | 2i + 1 |
| Right child of i | 2i + 2 |
| Parent of i | floor((i - 1) / 2), for i > 0 |
| Best fit | Complete or nearly complete trees |
| Worst fit | Skewed trees: a 3-node right chain needs 7 slots |
You should already be comfortable with these ideas:
The lesson uses two ways to represent the same binary tree.
left reference, and a right reference.In a linked-node tree, the root reference is the entry point. A missing child is stored as null.
In a zero-based array representation:
0.i has conceptual child positions:
2i + 12i + 2i has parent position:These formulas describe positions, not values. A value such as A, 7, or cat does not affect where its children belong.
Use this tree throughout the main example:
1 A
2 / \
3 B C
4 / \
5 D EThe intended child relationships are:
| Node | Left child | Right child |
|---|---|---|
| A | B | C |
| B | D | E |
| C | null | null |
| D | null | null |
| E | null | null |
Each node has three fields:
1Node:
2 value
3 left
4 rightThe tree begins at the root reference:
1root -> AThe full linked structure is:
1A.left -> B
2A.right -> C
3
4B.left -> D
5B.right -> E
6
7C.left -> null
8C.right -> null
9
10D.left -> null
11D.right -> null
12
13E.left -> null
14E.right -> nullPlace the same nodes in level-order positions.
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Value | A | B | C | D | E |
1[A, B, C, D, E]Start at index 0.
A is at index 0.2(0) + 1 = 1, which stores B.2(0) + 2 = 2, which stores C.Inspect B at index 1.
2(1) + 1 = 3, which stores D.2(1) + 2 = 4, which stores E.Build both representations of the example.
Create node A.
1root -> A
2
3A.left -> B
4A.right -> CAt this point, A correctly identifies its two intended children.
Create nodes B, C, D, and E. Then assign child references.
1A.left -> B
2A.right -> C
3
4B.left -> D
5B.right -> E
6
7C.left -> null
8C.right -> null
9
10D.left -> null
11D.right -> null
12
13E.left -> null
14E.right -> nullA null reference is not a missing node record. It states that the corresponding child does not exist.
Place each node in its zero-based level-order position.
Nodes take zero-based level-order slots: A at 0, B at 1, C at 2, D at 3, E at 4. B's children land at 2(1) + 1 = 3 and 2(1) + 2 = 4.
The first level uses index 0.
The next level uses indices 1 and 2.
The next available positions for children of B are 3 and 4.
1[A, B, C, D, E]Check B at index 1.
1leftIndex(1) = 2(1) + 1 = 3
2rightIndex(1) = 2(1) + 2 = 4Index 3 stores D, and index 4 stores E.
E is at index 4.
1parentIndex(4) = floor((4 - 1) / 2)
2 = floor(3 / 2)
3 = 1Index 1 stores B, which is E's parent.
Compare a different small tree:
1 A
2 \
3 CLinked nodes represent it directly:
1A.left -> null
2A.right -> CThe array must preserve A's missing left-child position:
| Index | 0 | 1 | 2 |
|---|---|---|---|
| Value | A | null | C |
1[A, null, C]If we wrote [A, C], then C would be at index 1, which is the left-child position. The shape would change.
Look at any occupied array position i.
Its tree relationships always follow the same rule:
2i + 1.2i + 2.i > 0, its parent position is floor((i - 1) / 2).The key invariant of a zero-based binary-tree array representation is that these formulas determine each position's tree relationships.
For example, at index 1:
1left = 2(1) + 1 = 3
2right = 2(1) + 2 = 4For index 4:
1parent = floor((4 - 1) / 2) = 1The formulas remain true even when a child position is outside the array or contains null. In that case, the position is conceptual, but no existing child is stored there.
When reading a child from an array, two checks are required:
null.Do not infer value ordering from array positions. For example:
1[7, 2, 9]is a valid tree shape representation. It means 7 is the root, 2 is its left child, and 9 is its right child. It does not claim that the values are sorted.
Convert a zero-based level-order array with null placeholders into linked nodes.
For this input:
1[A, B, C, D, E]we need these linked nodes:
1A.left -> B A.right -> C
2B.left -> D B.right -> EA direct construction uses two passes.
For every array index:
null, leave the corresponding node slot as null.For the example:
| Index | Array value | Node slot after pass 1 |
|---|---|---|
| 0 | A | node A |
| 1 | B | node B |
| 2 | C | node C |
| 3 | D | node D |
| 4 | E | node E |
For each non-null node at index i:
left = 2i + 1.right = 2i + 2.For B at index 1:
1left = 3 -> attach D
2right = 4 -> attach EThe construction preserves array positions. A null placeholder does not shift later nodes left.
Linked nodes represent arbitrary tree shapes with null references for missing children. An array uses consecutive positions when the tree is complete or nearly complete. A sparse or skewed shape can leave many unused positions.
For example, a right-skewed path has these occupied positions:
1A -> right B -> right C
2
3A at 0
4B at 2
5C at 6Indices 1, 3, 4, and 5 are unused.
The helpers use zero-based indices.
1function leftIndex(i):
2 input: integer i, where i >= 0
3 returns: the conceptual left-child index of position i
4 mutates: nothing
5
6 return 2 * i + 11function rightIndex(i):
2 input: integer i, where i >= 0
3 returns: the conceptual right-child index of position i
4 mutates: nothing
5
6 return 2 * i + 21function parentIndex(i):
2 input: integer i, where i > 0
3 returns: the parent index of position i
4 mutates: nothing
5
6 return floor((i - 1) / 2)A node has a value and two references.
1record Node:
2 value
3 left
4 rightThe conversion function expects a position-preserving zero-based level-order array. Each entry is either a value or null. A non-null entry below the root must have a non-null parent entry at its computed parent position.
1function arrayToLinkedTree(values):
2 input: zero-based array values containing values or null placeholders
3 returns: root Node reference, or null when values is empty or values[0] is null
4 mutates: does not modify values
5
61. if length(values) == 0:
72. return null
8
93. nodes = new array of length(values), filled with null
10
114. for i from 0 to length(values) - 1:
125. if values[i] is not null:
136. nodes[i] = new Node(values[i], null, null)
14
157. for i from 0 to length(values) - 1:
168. if nodes[i] is null:
179. continue
18
1910. left = leftIndex(i)
2011. right = rightIndex(i)
21
2212. if left < length(values) and nodes[left] is not null:
2313. nodes[i].left = nodes[left]
24
2514. if right < length(values) and nodes[right] is not null:
2615. nodes[i].right = nodes[right]
27
2816. return nodes[0]The first loop creates node records. The second loop changes only left and right references.
Use the original input:
1values = [A, B, C, D, E]Line 1: length(values) is 5, so do not return.
Line 3: Create the node-slot array.
1nodes = [null, null, null, null, null]Line 4, i = 0:
Line 5: values[0] is A, not null.
Line 6: Create node A.
1nodes = [A, null, null, null, null]Line 4, i = 1:
Create node B.
1nodes = [A, B, null, null, null]Line 4, i = 2:
Create node C.
1nodes = [A, B, C, null, null]Line 4, i = 3:
Create node D.
1nodes = [A, B, C, D, null]Line 4, i = 4:
Create node E.
1nodes = [A, B, C, D, E]The first loop ends.
At the start of the second loop, all nodes have:
1left = null
2right = nullLine 7, i = 0:
Line 8: nodes[0] is A, so do not continue.
Line 10: left = leftIndex(0) = 1
Line 11: right = rightIndex(0) = 2
Line 12: 1 < 5 and nodes[1] is B.
Line 13: Set A.left = B.
Line 14: 2 < 5 and nodes[2] is C.
Line 15: Set A.right = C.
1A.left -> B
2A.right -> CLine 7, i = 1:
nodes[1] is B.
Line 10: left = leftIndex(1) = 3
Line 11: right = rightIndex(1) = 4
Line 12: 3 < 5 and nodes[3] is D.
Line 13: Set B.left = D.
Line 14: 4 < 5 and nodes[4] is E.
Line 15: Set B.right = E.
1B.left -> D
2B.right -> ELine 7, i = 2:
nodes[2] is C.
1left = leftIndex(2) = 5
2right = rightIndex(2) = 6Neither index is less than 5, so lines 13 and 15 do not run.
1C.left -> null
2C.right -> nullLine 7, i = 3:
D has conceptual child positions 7 and 8, both outside the array. Its references stay null.
Line 7, i = 4:
E has conceptual child positions 9 and 10, both outside the array. Its references stay null.
Line 16: Return nodes[0], which is A.
The returned root reaches the complete linked tree:
1 A
2 / \
3 B C
4 / \
5 D EWe need to show that arrayToLinkedTree returns a linked-node tree with the same parent-child relationships as the input array.
Before the first loop, nodes contains only null entries.
During the first loop, each non-null values[i] creates exactly one node at nodes[i]. Each null placeholder leaves nodes[i] as null.
After this loop:
Consider one iteration of the second loop at index i.
If nodes[i] is null, there is no tree node at that position. The algorithm changes nothing and continues.
If nodes[i] is non-null, the algorithm computes:
1left = 2i + 1
2right = 2i + 2These are exactly the zero-based child positions required by the array representation invariant.
For each computed position, the algorithm assigns a child reference only when:
nodes entry is non-null.Therefore:
nodes[i].left is assigned exactly the node stored at 2i + 1, when that child exists.nodes[i].right is assigned exactly the node stored at 2i + 2, when that child exists.null.Processing one node does not alter the value or position of any other node. The correct relationships already established for earlier indices remain correct.
The second loop processes every index from 0 through length(values) - 1.
Every non-null node position receives the correct left and right references according to the zero-based formulas. The returned nodes[0] is the root node when the root entry exists, or null when the input is empty or begins with null.
The returned linked-node tree represents the same tree shape and values as the position-preserving input array.
Let n be length(values).
Each helper performs a fixed amount of arithmetic:
12 * i + 1
22 * i + 2
3floor((i - 1) / 2)That is constant work.
O(1)O(1)Given a node reference, reading or assigning left or right performs one reference operation.
O(1)O(1)arrayToLinkedTree has two loops.
n array entries once.n node slots once.Each iteration performs constant work aside from the loop movement. The total work is proportional to 2n.
O(n)The function creates:
nodes array with n slots, andn linked-node records.Its auxiliary working array uses O(n) space. The returned linked nodes are the constructed output representation.
For n actual nodes:
O(n) node records.O(n) entries.null placeholders up to its highest occupied index.For the right-skewed path:
1A at 0, B at 2, C at 6the highest occupied index is 6, so the position-preserving array has seven entries even though the tree has only three nodes.
A traversal of either representation visits each existing node once.
O(n)Its extra workspace depends on the traversal:
O(h) call-stack space for tree height h.O(w) queue space for maximum width w.Incorrect lines:
1left = 2 * i
2right = 2 * i + 1Smallest exposing input:
1[A, B, C]At i = 0, the incorrect calculation gives:
1left = 2 * 0 = 0Wrong state:
1A.left -> AThe root points to itself.
Correction:
1left = 2 * i + 1
2right = 2 * i + 2For A at index 0, this gives child positions 1 and 2.
Incorrect line:
1return floor(i / 2)Exposing input:
1[A, B, C]At index 2, which stores C:
1floor(2 / 2) = 1Wrong result: the parent appears to be index 1, which stores B.
Correction:
1return floor((i - 1) / 2)Then:
1floor((2 - 1) / 2) = floor(1 / 2) = 0Index 0 stores A, the correct parent.
Incorrect assumption:
1If a position is null, remove it and shift later values left.Exposing input:
1A has right child C onlyCorrect position-preserving array:
1[A, null, C]Incorrect compacted array:
1[A, C]Wrong state:
1C is at index 1Index 1 is the left-child position, so this changes C into A's left child.
Correction: preserve the missing left position.
1[A, null, C]Incorrect assumption:
1A binary-tree array must be sorted.Exposing input:
1[7, 2, 9]Wrong result: reject the array because 2 appears after 7.
The entries describe this shape:
1 7
2 / \
3 2 9Correction: use indices to determine structural relationships. Do not use index order as a value-ordering rule.
| Tree | Linked-node root | Position-preserving array |
|---|---|---|
| Empty tree | null | [] |
| Single node A | A.left = null, A.right = null | [A] |
| A with left child B only | A.left = B, A.right = null | [A, B] |
| A with right child C only | A.left = null, A.right = C | [A, null, C] |
| Right path A → B → C through right links | direct right references | occupied positions 0, 2, 6 |
Implement these functions:
1leftIndex(i)
2rightIndex(i)
3parentIndex(i)
4arrayToLinkedTree(values)arrayToLinkedTree(values) receives a zero-based level-order array containing null placeholders and returns the linked-tree root.
Executable tests verify these inputs:
1["A", "B", "C", "D", "E"]
2["A", null, "C"]
3[]
4["A"]The tested contract requires:
leftIndex(i) = 2i + 1rightIndex(i) = 2i + 2parentIndex(i) = floor((i - 1) / 2) for i > 0null placeholders to remain structural positions rather than being removednull for absent children1class Node:
2 def __init__(self, value):
3 self.value, self.left, self.right = value, None, None
4
5def left_index(i):
6 return 2 * i + 1
7
8def right_index(i):
9 return 2 * i + 2
10
11def parent_index(i):
12 return (i - 1) // 2
13
14def array_to_linked_tree(values):
15 if not values:
16 return None
17 nodes = [Node(v) if v is not None else None for v in values] # pass 1
18 for i, node in enumerate(nodes): # pass 2
19 if node is None:
20 continue
21 l, r = left_index(i), right_index(i)
22 if l < len(values) and nodes[l] is not None:
23 node.left = nodes[l]
24 if r < len(values) and nodes[r] is not None:
25 node.right = nodes[r]
26 return nodes[0]
27
28def show(node):
29 if node is None:
30 return
31 l = node.left.value if node.left else "-"
32 r = node.right.value if node.right else "-"
33 print(f"{node.value} left={l} right={r}")
34 show(node.left)
35 show(node.right)
36
37show(array_to_linked_tree(["A", "B", "C", "D", "E"]))
38print("parent(4) =", parent_index(4))
39show(array_to_linked_tree(["A", None, "C"])) # the null keeps C a right child1public class Main {
2 static class Node {
3 String value;
4 Node left, right;
5 Node(String value) { this.value = value; }
6 }
7
8 static int leftIndex(int i) { return 2 * i + 1; }
9 static int rightIndex(int i) { return 2 * i + 2; }
10 static int parentIndex(int i) { return (i - 1) / 2; }
11
12 static Node arrayToLinkedTree(String[] values) {
13 if (values.length == 0) return null;
14 Node[] nodes = new Node[values.length];
15 for (int i = 0; i < values.length; i++) { // pass 1
16 if (values[i] != null) nodes[i] = new Node(values[i]);
17 }
18 for (int i = 0; i < values.length; i++) { // pass 2
19 if (nodes[i] == null) continue;
20 int l = leftIndex(i), r = rightIndex(i);
21 if (l < values.length && nodes[l] != null) nodes[i].left = nodes[l];
22 if (r < values.length && nodes[r] != null) nodes[i].right = nodes[r];
23 }
24 return nodes[0];
25 }
26
27 static void show(Node node) {
28 if (node == null) return;
29 String l = node.left != null ? node.left.value : "-";
30 String r = node.right != null ? node.right.value : "-";
31 System.out.println(node.value + " left=" + l + " right=" + r);
32 show(node.left);
33 show(node.right);
34 }
35
36 public static void main(String[] args) {
37 show(arrayToLinkedTree(new String[] {"A", "B", "C", "D", "E"}));
38 System.out.println("parent(4) = " + parentIndex(4));
39 show(arrayToLinkedTree(new String[] {"A", null, "C"})); // the null keeps C a right child
40 }
41}1#include <iostream>
2#include <string>
3#include <vector>
4using namespace std;
5
6struct Node {
7 string value;
8 Node *left = nullptr, *right = nullptr;
9 Node(string v) : value(v) {}
10};
11
12int leftIndex(int i) { return 2 * i + 1; }
13int rightIndex(int i) { return 2 * i + 2; }
14int parentIndex(int i) { return (i - 1) / 2; }
15
16// "" marks a null placeholder. The caller owns nothing; nodes live in the vector.
17Node* arrayToLinkedTree(const vector<string>& values, vector<Node>& store) {
18 if (values.empty()) return nullptr;
19 int n = values.size();
20 store.reserve(n); // keeps pointers stable
21 vector<Node*> nodes(n, nullptr);
22 for (int i = 0; i < n; i++) { // pass 1
23 if (!values[i].empty()) {
24 store.emplace_back(values[i]);
25 nodes[i] = &store.back();
26 }
27 }
28 for (int i = 0; i < n; i++) { // pass 2
29 if (!nodes[i]) continue;
30 int l = leftIndex(i), r = rightIndex(i);
31 if (l < n && nodes[l]) nodes[i]->left = nodes[l];
32 if (r < n && nodes[r]) nodes[i]->right = nodes[r];
33 }
34 return nodes[0];
35}
36
37void show(Node* node) {
38 if (!node) return;
39 cout << node->value << " left=" << (node->left ? node->left->value : "-")
40 << " right=" << (node->right ? node->right->value : "-") << endl;
41 show(node->left);
42 show(node->right);
43}
44
45int main() {
46 vector<Node> s1, s2;
47 show(arrayToLinkedTree({"A", "B", "C", "D", "E"}, s1));
48 cout << "parent(4) = " << parentIndex(4) << endl;
49 show(arrayToLinkedTree({"A", "", "C"}, s2)); // the null keeps C a right child
50}1class Node {
2 constructor(value) {
3 this.value = value;
4 this.left = this.right = null;
5 }
6}
7
8const leftIndex = (i) => 2 * i + 1;
9const rightIndex = (i) => 2 * i + 2;
10const parentIndex = (i) => Math.floor((i - 1) / 2);
11
12function arrayToLinkedTree(values) {
13 if (values.length === 0) return null;
14 const nodes = values.map((v) => (v === null ? null : new Node(v))); // pass 1
15 nodes.forEach((node, i) => { // pass 2
16 if (node === null) return;
17 const l = leftIndex(i);
18 const r = rightIndex(i);
19 if (l < values.length && nodes[l] !== null) node.left = nodes[l];
20 if (r < values.length && nodes[r] !== null) node.right = nodes[r];
21 });
22 return nodes[0];
23}
24
25function show(node) {
26 if (node === null) return;
27 const l = node.left ? node.left.value : '-';
28 const r = node.right ? node.right.value : '-';
29 console.log(`${node.value} left=${l} right=${r}`);
30 show(node.left);
31 show(node.right);
32}
33
34show(arrayToLinkedTree(['A', 'B', 'C', 'D', 'E']));
35console.log(`parent(4) = ${parentIndex(4)}`);
36show(arrayToLinkedTree(['A', null, 'C'])); // the null keeps C a right childLinked nodes store a value and two references, so any shape costs one node per element. An array finds children by arithmetic and needs no pointers, but sparse trees waste slots on nulls.
They hold the missing positions. For a tree where A has only a right child C, the array is [A, null, C]. Writing [A, C] would put C at index 1, the left-child slot, and change the shape.
Each level doubles the slot count even when only one node is used. A right chain A, B, C sits at indices 0, 2 and 6, so seven slots hold three nodes.
No. The indices encode shape, not value order. The array [7, 2, 9] is a root 7 with left child 2 and right child 9.
Create a node for every non-null entry. Then for each node at index i, attach the nodes at 2i + 1 and 2i + 2 if they are inside the array and not null. This takes O(n) time.