Definition

An n-ary tree extends the concept of binary tree to n-ary tree.

A binary tree is a rooted tree in which each node has no more than 2 children. Let's extend this definition to N-ary tree. If a tree is a rooted tree in which each node has no more than N children, it is called N-ary tree.

Trie is one of the most frequently used N-ary trees.

Also, a binary tree is a special form of a N-ary tree. In the following sections, we will extend what we have learned about binary trees to N-ary trees.

Traversal

Retrospect - Traverse a Binary Tree:

• Preorder Traversal: Visit the root node, then traverse the left subtree and finally traverse the right subtree.
• Inorder Traversal: Traverse the left subtree, then visit the root node and finally traverse the right subtree.
• Postorder Traversal: Traverse the left subtree, then traverse the right subtree and finally visit the root node.
• Level-order Traversal: Traverse the tree level by level.

Note that here is no standard definition for in-order traversal in n-ary trees.

To generalize the above to n-ary trees, you simply replace the steps:

Traverse the left subtree.... Traverse the right subtree..

with

For each child:
      Traverse the subtree rooted at that child by recursively calling the traversal function

We assume that the for-loop will iterate through the children in the order they are found in the data-structure: typically, in left-to-right order, for a diagram such as below.

Preorder Traversal

• Preorder Traversal

In an N-ary tree, preorder means visit the root node first and then traverse the subtree rooted at its children one by one. For instance, the preorder of the 3-ary tree above is: A->B->C->E->F->D->G.

Postorder Traversal

• Postorder Traversal

In an N-ary tree, postorder means traverse the subtree rooted at its children first and then visit the root node itself. For instance, the postorder of the 3-ary tree above is: B->E->F->C->G->D->A.

Level-order Traversal

• Levelorder Traversal

Level-order traversal in an N-ary tree is the same with a binary tree. Typically, when we do breadth-first search in a tree, we will traverse the tree in level order. For instance, the level-order of the 3-ary tree above is: A->B->C->D->E->F->G.

Recursion

• N-Ary Max Depth
• N-Ary Tree into Binary Tree
• Serialize/Deserialize N-Ary Tree

"Top-down" Solution

"Top-down" means that in each recursion level, we will visit the node first to come up with some values, and pass these values to its children when calling the function recursively.

1. return specific value for null node
2. update the answer if needed                              // answer <-- params
3. for each child node root.children[k]:
4.      ans[k] = top_down(root.children[k], new_params[k])  // new_params <-- root.val, params
5. return the answer if needed                              // answer <-- all ans[k]

"Bottom-up" Solution

"Bottom-up" means that in each recursion level, we will firstly call the functions recursively for all the children nodes and then come up with the answer according to the return values and the value of the root node itself.

1. return specific value for null node
2. for each child node root.children[k]:
3.      ans[k] = bottom_up(root.children[k])    // call function recursively for all children
4. return answer                                // answer <- root.val, all ans[k]