![\"N-ary](\"https:\/\/i0.wp.com\/theoryofcoding.com\/wp-content\/uploads\/2018\/01\/n-ary-tree-1.jpg?ssl=1\")
<\/a>The above example is a N-ary tree with N = 3. You can observe that each node has no more than 3 children.<\/p>\nIn many scenarios, having a binary tree many not be enough as a situation can often lead to more than 2 situations. In such cases, we must form a N-ary tree of sufficiently large N.<\/p>\n
Implementing N-ary tree using structures<\/h2>\n
Implementing N-ary tree is very simple. It is even more easy if you already know how to implement a Trie Tree<\/a>. Now, in the case of binary tree, the node structure was like this –<\/p>\n Having two references was enough for us then because we knew we would have at most 2 children. Now, we can have at most N children. How will you store a collection of N references? By using an array! In the case of Java, I’d like to use an ArrayList<\/em> rather than an array. In the case of C++, I’d suggest you go for a C++ STL vector<\/em>. So now our node structure will look like this –<\/p>\n Storing the value of N inside the node will enable us to put a restriction on the number of children. So we will add methods inside our newly formed NaryTreeNode<\/em> class to manipulate the member variables. Some important methods would be –<\/p>\n Also, don’t forget to add a constructor to your class! Now you are all set to write the code for N-ary tree. Try to code it, this is something you should be able to code in 1-3 attempts. You can refer to my code below if you get stuck –<\/p>\n I have added a helper method for printing the tree so that the tree can be printed more legibly based on the depth of nodes. I have also modified the addChild()<\/em> method a little. It only accepts the new child’s label as it’s N<\/em> value can be deduced from the parent node. The code should be easy to understand. Do leave a comment if you have any doubts \ud83d\ude42<\/p>\n Remember you can implement a binary tree using arrays. Similarly, you can also implement an N-ary tree using arrays. It is very similar to how you would do it in the case of binary trees, so here the formula for computing child node and parent node changes.<\/p>\n\nclass TreeNode {\n String label;\n Node leftChild, rightChild;\n}\n<\/pre>\n\nclass NaryTreeNode {\n String label;\n ArrayList<NaryTreeNode> children;\n int n;\n}\n<\/pre>\n\n
\n<\/div>\n
\n Pure
\n Elements
\n Metals
\n Metalloids
\n Non-metals
\n Compounds
\n Water
\n Carbon dioxide
\n Salt
\n Mixture
\n Homogeneous
\n Air
\n Vinegar
\n Heterogeneous
\n Colloids
\n Suspensions
\n[\/code]\n<\/div><\/div><\/div>\nImplementing N-ary tree using arrays<\/h2>\n