Introduction

You can represent a general non-binary tree in a one-dimensional vector if each node stores indices instead of pointers. The most practical array-based technique is the first-child / next-sibling representation, optionally with lastChild to make appends cheaper.

Use child and sibling indices instead of nested lists

The core idea is simple: every node lives in one flat vector, and relationships are expressed by integer indices into that vector.

A node record might store:

• the node's value
• the index of its first child
• the index of its next sibling
• optionally the index of its last child

That layout lets one vector represent a full general tree without storing a variable-length child array inside every node.

For example, if A has children B and C, and B has child D, the vector can look like this:

This is a flat structure, but it still preserves tree shape.

Appending a child is straightforward

The main operation is adding a new child to a parent. Append the new node to the vector, then update the parent's child links.

1from dataclasses import dataclass
2
3@dataclass
4class Node:
5    value: str
6    first_child: int = -1
7    next_sibling: int = -1
8    last_child: int = -1
9
10
11nodes = []
12
13def add_node(value):
14    nodes.append(Node(value))
15    return len(nodes) - 1
16
17
18def add_child(parent_index, child_value):
19    child_index = add_node(child_value)
20    parent = nodes[parent_index]
21
22    if parent.first_child == -1:
23        parent.first_child = child_index
24        parent.last_child = child_index
25    else:
26        nodes[parent.last_child].next_sibling = child_index
27        parent.last_child = child_index
28
29    return child_index

This gives you O(1) append-to-children behavior if last_child is maintained.

Traversal follows first child, then sibling chain

Tree traversal works by visiting a node, then recursively walking its child list through sibling links.

1def print_tree(index, depth=0):
2    while index != -1:
3        node = nodes[index]
4        print("  " * depth + node.value)
5        if node.first_child != -1:
6            print_tree(node.first_child, depth + 1)
7        index = node.next_sibling
8
9
10root = add_node("A")
11b = add_child(root, "B")
12c = add_child(root, "C")
13add_child(b, "D")
14
15print_tree(root)

This prints the tree in depth-first order while using only one flat vector for storage.

Why this representation is useful

The biggest advantages are:

• contiguous storage
• no pointer allocation per edge
• stable integer references while the vector layout is controlled
• good fit for serialization or compact in-memory formats

This representation is especially useful in parsers, scene graphs, compact AST storage, and systems where you want tree structure without a heap object graph for every child list.

The main tradeoff is readability. Pointer-based or list-based tree nodes are often easier to understand at first glance. The array representation is better when compactness or flat storage matters more than convenience.

Common Pitfalls

• Forgetting that child traversal requires following the sibling chain, not only the first child pointer.
• Appending children without updating the previous last child's next_sibling.
• Using vector indices carelessly and breaking relationships when nodes are removed or reordered.
• Assuming this layout supports constant-time random access to the nth child without walking siblings.
• Choosing a flat indexed representation when a simpler list-of-children structure would be easier for the actual problem.

Summary

• A non-binary tree can be stored in one vector by keeping child and sibling indices in each node.
• The first-child / next-sibling representation is the standard compact approach.
• Adding lastChild makes child append operations efficient.
• Traversal works by recursing through the first child and then walking sibling links.
• This design is best when compact flat storage matters more than a simple object model.