- Introduction<\/a><\/li>
- 1. Naive Approach<\/a><\/li>
- 2. Improved Approach<\/a><\/li>
- Sample Implementation<\/a><\/li><\/ul>
- 3. Optimal Approach<\/a><\/li>
- Advantages<\/a><\/li>
- Sample Implementation<\/a><\/li><\/ul>
- Additional Resources<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
Introduction<\/h2>\n\n\n\n
N-ary trees<\/strong> are tree data structures that allow us to have up to n<\/strong> children nodes for each of the nodes, differing from the standard binary trees which allow only up to 2<\/strong> children nodes for each node.<\/p>\n\n\n\n
<\/figure>\n\n\n\n
The above picture shows an example of an n-ary tree. Observe that in the example, the tree has a total of n = 11 nodes, where some nodes have 3 children, some have only 1 child, and some don\u2019t have any children at all. This tree is an N-ary tree where N >= 3 because the number of children of the tree ranges from 0 to 3.<\/p>\n\n\n\n
1. Naive Approach<\/h2>\n\n\n\n
We basically need to store 2 pieces of information to completely represent an N-ary tree.<\/p>\n\n\n\n
- The value of the node<\/li>
- The addresses of all its children nodes.<\/li><\/ul>\n\n\n\n
We can build a class or struct to store this information effectively. For storing the latter information, we can use an Array or LinkedList<\/strong>. Both these data structures will however have some shortcomings which we will discuss below:<\/p>\n\n\n\n
- Since the number of children of a node is not known<\/strong> beforehand, we can store only a fixed number of children\u2019s addresses in an array<\/strong>.<\/li>
- LinkedList<\/strong> won\u2019t allow us to randomly access any child\u2019s address, so it will be expensive in terms of complexity.<\/li><\/ul>\n\n\n\n
2. Improved Approach<\/h2>\n\n\n\n
To improve the shortcomings of the naive approach, we can use Dynamic Arrays<\/strong> to store the addresses of the children of the nodes. Using this approach, we can randomly access any child\u2019s address in O(1) as well as don\u2019t have to know the number of children of each node beforehand.<\/p>\n\n\n\n
Sample Implementation<\/span><\/h3>\n\n\n\n
class TreeNode {\n int value;\n vector<TreeNode*> children;\n};<\/pre>\n\n\n\n3. Optimal Approach<\/h2>\n\n\n\n
The optimal way to implement a Node for an N-ary Tree will be to use the First Child\/Next Sibling representation. The steps to implement this are as follows:<\/p>\n\n\n\n
- For each node, we link the children of the common parent(siblings) from left to right order.<\/li>
- Then we will remove the links from the parent to all the children, except for the first child node.<\/li><\/ul>\n\n\n\n
The focus of this representation is that since we have a link between children, we do not need extra links from parents to all the children.<\/p>\n\n\n\n
Advantages<\/h3>\n\n\n\n
- Since no extra links are required, we can consider this to be a memory-efficient implementation.<\/li>
- All the nodes are of constant size, and no dynamic arrays or linked lists are required.<\/li>
- With the above representation, we can convert all n-ary trees into a binary tree representation, which is a topic we are more familiar with.<\/li>
- Many algorithms can be expressed and implemented more easily because we can consider the N-ary tree to be a binary tree.<\/li><\/ul>\n\n\n\n
Sample Implementation<\/h3>\n\n\n\n
struct TreeNode {\n int value;\n TreeNode* firstChild;\n TreeNode* nextSibling;\n};<\/pre>\n\n\n\nAdditional Resources<\/h2>\n\n\n\n
- Tree Data Structure<\/a><\/li>
- Coding Interview Questions<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"Introduction N-ary trees are tree data structures that allow us to have up to n children nodes for…\n","protected":false},"author":5,"featured_media":5043,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[681],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4865"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=4865"}],"version-history":[{"count":6,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4865\/revisions"}],"predecessor-version":[{"id":23625,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4865\/revisions\/23625"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/5043"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=4865"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=4865"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=4865"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
- Tree Data Structure<\/a><\/li>
- LinkedList<\/strong> won\u2019t allow us to randomly access any child\u2019s address, so it will be expensive in terms of complexity.<\/li><\/ul>\n\n\n\n
- Since the number of children of a node is not known<\/strong> beforehand, we can store only a fixed number of children\u2019s addresses in an array<\/strong>.<\/li>
- Sample Implementation<\/a><\/li><\/ul>
- 3. Optimal Approach<\/a><\/li>
- 1. Naive Approach<\/a><\/li>
![\"n-ary](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Image1-4-1024x569.png\")
<\/figure>\n\n\n\n