# Access a tree by level without traversing

I need a tree structure that works roughly like the following

• for each new child I need to match it (with some criteria) with a parent from the previous level only

• when the tree is completely initialized, for each leaf I need to find the first parent ancestor that has siblings, i.e. the node just after the branching point.

While the latter is pretty easy with a tipical tree structure, for the first I'd like to just access all nodes of a layer without traversing the whole tree (even with BFS). Does this have a name?

I'm thinking to just keep track of level number for each node and build a second structure to represent levels.

• The wording is slightly unusual in my eyes: for a child, there should be exactly one parent, which should be known/well-defined on insertion(new): are you talking about potential parents to select from? First parent might be first ancestor. – greybeard Jan 28 '18 at 9:42
• You're right, I meant ancestor – filippo Jan 28 '18 at 11:20

To support the operations mentioned - especially level-order traversal (or walk) - in time bounded by the depth, you don't need an extra attribute for each node.

For a "semi-static" tree¹, you could use an array of nodes to store it:
For every level, keep the index just beyond.
For every node, keep parent, for non-leaf nodes, children ("first" child), too:
siblings are successive nodes with same parent.

For a "dynamic" tree, modify the [typical] tree structure keeping children, siblings and optionally parent to support level-order traversal:
Change sibling to next in same level - not a sibling iff different parent.
You may need support for first in level, or "the list of nodes in the same level" to be circular to be able to access all of them starting from any-one thereof.

[1]: semi-static tree: only structural change is addition of nodes.
(The task sketched may have another restriction: no node with children will get another child once a different node gets one.)
(or even static: [once] the tree is completely initialized)

If it’s a complete tree, you could use an array to store it. Accessing parents, siblings, and children would be quite simple and you wouldn’t have to traverse the tree.

• It's not complete, any node could have any number of children. The only thing I know in advance is the number of layers. Another thing I can exploit is that once it's initialized it's fixed, and I only need to climb it backwards from leaves looking for branching points. – filippo Nov 29 '17 at 6:46