Access a tree by level without traversing
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)