N-ary Trees and Vector Representation in Java

Part of: Java for Beginners › N-ary trees and vector-based representation

Real-World Modeling

N-ary Trees: Beyond Binary

Unlike a binary tree, a node can have 0, 1, 2… K children. A filesystem, an HTML DOM tree, or a category hierarchy are all general trees.

The degree (number of children) is neither bounded nor uniform: home has 2 children, etc/ has 5, while bin/ and var/ are leaves with 0 children. That asymmetry cannot be modeled with a binary tree.

Implementation Dilemma

Fixed Children Array vs Dynamic List

Nodo[] hijos = new Nodo[MAX] reserves fixed memory upfront: brutal on leaf nodes. List<Nodo> hijos grows as needed, at the cost of an ArrayList object overhead per node.

Option A · Fixed Array Nodo[] hijos = new Nodo[8]

The etc/ node (5 real children) reserves 8 pointers upfront:

nginx ssh hosts resolv.conf ssl null null null

3 / 8 wasted cells (37.5%)

The leaf node bin/ (0 children) reserves the same 8 cells:

null null null null null null null null

8 / 8 wasted cells (100%)

Option B · Dynamic List List<Nodo> hijos = new ArrayList<>()

The etc/ node (5 children): the list grows to exactly 5 elements.

nginx ssh hosts resolv.conf ssl

0 wasted cells, but +ArrayList object overhead per node

The leaf node bin/ (0 children): the list stays empty.

(empty)

0 wasted cells, yet still carries one ArrayList object per leaf

Structural Transformation

Left-Child Right-Sibling (LCRS)

Each node only needs two references: primerHijo (leftmost child) and siguienteHermano (next node to its right at the same level). Drag to transform the N-ary tree into a strict binary tree.

N-ary View Binary View (LCRS)

primerHijo siguienteHermano

At 0%: the traditional N-ary tree, each node with a list of children. At 100%: only the leftmost child hangs downward (primerHijo); the rest chain to the right (siguienteHermano), forming a strict binary tree.

Depth-First Traversal

Preorder: Parent Before Its Children

Visit the node, then walk each subtree left to right. The same traversal, applied to the LCRS version, yields the exact same sequence.

N-ary Tree

LCRS Tree (binary)

1: A 2: B 3: E 4: F 5: C 6: D

Compact Memory Representation

Parent Vector: int[] padre

Nodes are numbered 0 through N-1. padre[i] stores the parent index of node i (the root is -1). Click any table cell to highlight the relationship in the tree.

i	0	1	2	3	4
padre[i]	-1	0	0	0	1

Click an index in the table to see its parent-child relationship.

Algorithms over the Vector

Climbing to Root: O(1) vs Listing Children: O(N)

Climbing to the root is instant: while (p != -1) p = padre[p];. Listing a node’s children requires scanning the whole array for padre[j] == node, in O(N).

Selected node:

0-1

Pick a node and an operation.

Complete Trees and Index Arithmetic

Complete Ternary Tree: No Pointers, Just Formulas

If the tree is a complete K-ary tree, each node’s position is computed: the j-th child of i sits at 3i + j; the parent of i sits at ⌊(i-1) / 3⌋. Click a tree node or an array cell.

hijo_j(i) = 3×i + j (j = 1, 2, 3) padre(i) = ⌊(i − 1) / 3⌋

Node 1: parent = 0 · children = 4, 5, 6 (3×1+1, 3×1+2, 3×1+3)