Definition


In the previous article, we focused more on binary 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.

Here is an example of 3-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 learnt about binary trees to N-ary trees.

Tree Traversal


A binary tree can be traversed in preorder, inorder, postorder or level-order. Among these traversal methods, preorder, postorder and level-order traversal are suitable to be extended to a N-ary tree.

Retrospect - Traverse a Binary Tree

  1. Preorder Traversal:
    visit the root node, then traverse the left subtree and finally traverse the right subtree.

  2. Inorder Traversal:
    traverse the left subtree, then visit the root node and finally traverse the right subtree.

  3. Postorder Traversal:
    traverse the left subtree, then traverse the right subtree and finally visit the root node.

  4. Level-order Traversal: traverse the tree level by level.

1. Preorder Traversal

In a 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.

2. Postorder Traversal

In a 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.

3. Level-order Traversal

Level-order traversal in a 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.

Classical Recursion Solution


We talked about how to solve tree related problems recursively in previous article. In that article, we focused on binary trees but the idea can also be extended to a N-ary tree.

Make sure that you have read (Solve Tree Problems Recursively) before reading the following contents.

1. "Top-down" Solution

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

A typical "top-down" recursion function top_down(root, params) works like this:

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]

2. "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.

A typical "bottom-up" recursion function bottom_up(root) works like this:

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]

Convert a N-ary Tree to a Binary Tree


There are a lot of solutions to convert a N-ary tree to a binary tree. We only introduce one classical solution.

The strategy follows two rules: 1. The left child of each node in the binary tree is the next sibling of the node in the N-ary tree. 2. The right child of each node in the binary tree is the first child of the node in the N-ary tree.

Here is an example to help you understand this strategy:

!?!../Documents/Nary_Tree_to_Binary_Tree.json:1024,640!?!

Using this strategy, you can simply convert a N-ary tree to a binary tree recursively. Also, you can easily recover the N-ary tree from the binary tree you converted.

The recursion recovery strategy for each node is: 1. Deal with its children recursively. 2. Add its left child as the next child of its parent if it has a left child. 3. Add its right child as the first child of the node itself if it has a right child.

Here is an example to help you understand this strategy:

!?!../Documents/Binary_Tree_to_Nary_Tree.json:1024,640!?!

More information about this problem can be found in the exercise Serialize and Deserialize N-ary Tree II. There are a lot of different solutions for this problem. You can solve this problem in your own way.

Conclusion


The goal of this article is to introduce the basic idea of a N-ary tree. Actually, a binary tree is just a special form of a N-ary tree and the solution for a problem related with a N-ary tree is quite similar with what we have done with a binary tree. Therefore, we can extend what we learnt about a binary tree to a N-ary tree.

We also provide some exercise for you to further understand a N-ary tree in the following sections.