One node, many children
A binary tree limits each node to two children. An N-ary tree allows zero or more children per node. The root A has three children. With only two fixed links, D has no place left.
A binary tree limits each node to two children. An N-ary tree allows zero or more children per node.
The root A has three children. With only two fixed links, D has no place left.
A binary tree limits each node to two children. An N-ary tree allows zero or more children per node. The root A has three children. With only two fixed links, D has no place left.
Each node stores just two references: firstChild and nextSibling.
A points only to B; B links to C and C to D.
It is not a binary search tree: the links are relationships, not comparisons.
Each node stores just two references: firstChild and nextSibling. A points only to B; B links to C and C to D. It is not a binary search tree: the links are relationships, not comparisons.
To list the children of A, the walk jumps just once through firstChild and lands on B.
While child is not null, the while loop prints its value: B.
To list the children of A, the walk jumps just once through firstChild and lands on B. While child is not null, the while loop prints its value: B.
Then it moves along nextSibling: it prints C and then D, without returning to A.
It follows the sibling chain until null and the loop ends: the number of children does not matter.
Then it moves along nextSibling: it prints C and then D, without returning to A. It follows the sibling chain until null and the loop ends: the number of children does not matter.
Each node gets an index from 0 to 4; labels[i] stores its value.
parents[i] stores the index of the parent of node i. The root has no parent: it stores -1.
Each node gets an index from 0 to 4; labels[i] stores its value. parents[i] stores the index of the parent of node i. The root has no parent: it stores -1.
Before walking, validateLink checks that every index exists or is -1.
If parents[4] were 7, an IndexOutOfBoundsException is thrown: bad input is rejected, not repaired.
Before walking, validateLink checks that every index exists or is -1. If parents[4] were 7, an IndexOutOfBoundsException is thrown: bad input is rejected, not repaired.
From E (index 4), reading parents[current] climbs one level in O(1).
E climbs to B and B climbs to A: each jump adds one to the depth.
At A it reads -1: the root, depth 2. A cycle would make the climb endless.
From E (index 4), reading parents[current] climbs one level in O(1). E climbs to B and B climbs to A: each jump adds one to the depth. At A it reads -1: the root, depth 2. A cycle would make the climb endless.
With firstChild and nextSibling, two references are enough for any number of children.
With vectors, relationships are numbers: better locality and the parent in O(1), with validated indices.
With firstChild and nextSibling, two references are enough for any number of children. With vectors, relationships are numbers: better locality and the parent in O(1), with validated indices.