### 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

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.

#### 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.