Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
Program 
also defines three functions for manipulating
the root of an N-ary tree.
The first, Key, is an accessor which returns a reference to the
object contained in the root node of the tree.
Clearly, this operation is not defined for the empty tree.
If the tree is not empty, the running time of this routine is O(1).
The purpose of AttachKey is to insert the specified object into a given N-ary tree at the root node. This operation is only defined for an empty tree. The AttachKey routine takes as its lone argument a reference to the object to be inserted in the root node and makes the key member variable point at the given object. Since the node is no longer empty, it must have exactly N subtrees. Therefore, N new empty subtrees are created and attached to the node. The running time is O(N) since N subtrees are created, and the running time of the constructor for an empty N-ary tree takes O(1).
Finally, DetachKey is used
to remove the object from the root of a tree.
In order that the tree which remains still conforms
to Definition ,
it is only permissible to remove the root from a leaf node.
And upon removal, the leaf node becomes an empty tree.
The implementation given in Program
throws an exception if an attempt is made to remove the root
from a non-leaf node.
Otherwise, the node is a leaf which means that its N subtrees are all empty.
When the root is detached,
all the subtrees are deleted.
The running time of this routine is clearly O(N)
since there are N empty subtrees to be deleted
and the cost of deleting an empty N-ary tree is constant.
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.