N-ary tree : Way to store hierarchical data
Till now we have learned about binary tree and binary search tree. There is one more form of tree that is N-ary tree or N-ary data structure. As name suggests, Nary tree is a tree where each node has N children. Advance implementations of Nary trees can have flexibility of having different N for each node of the tree. The tree which we will implement will be one such tree. Figure below shows N-ary tree
What are the usage or applications of N-ary tree or N-ary data structure? One application is to store hierarchical information such as organization charts, store inventories, comments threads with replies etc.
Let’s see how node of a n-ary tree looks like:
In this definition, there is one void pointer representing data, this allows us to use the same tree for various data types. Close of C++ template class. In this pointer we put the data information. After that there is one integer nChildren which tells how many children this node has. And in the last we have a pointer to pointer which is nothing but array of pointers to all the children of this node.
Create a node in N-ary tree?
To create a node, we need to pass two parameters. One the number of child nodes this node has. If we don’t know, we can always send 0, later we will see how we can append a child to a parent node. Second is pointer to the data. Create node function looks like:
Pointer to data, for example an employee record, can be created as follows.
Delete N-ary tree
Deletion of tree happens in similar fashion as for binary tree, delete the children first and then the parent node. In Nary tree we will have multiple child nodes, so we have to go through all the nodes one by one and delete them. Once all child nodes are deleted, delete the parent node. Code to delete a tree is below
Append a child in N-ary tree
To append a child node of a parent node, we need to insert pointer of child to parent array of it’s children, However, we have already allocated the array for the parent node based on input provided at the time of creation of node. How can we increase that? There is one function in C called as realloc which takes two parameters, the old pointer and the size to allocated. It returns the new pointer with new size. Most of the time, the new pointer pointer points to the same memory location and old is done away with. However it is not necessary. New pointer may be pointing to a completely new memory location. So be safe and copy all information from old to new location using memcpy.
We will use this realloc function to reallocate our children array and at the end of the array, add the new child. Code is shown below.
Delete a child
To delete a node, we need to find it. Scan through tree and find the node in parent node’s children array. Delete node’s entry from children array of it’s parent.
Before deleting node, clarify with interviewer or requirement gatherer, what happens to children of current node. If children have to move to parent node of current, then do that before deleting the node.
If children have to be deleted with node, then recursively delete tree rooted at current node using method mentioned under ‘How to delete a n-ary tree?’
It is costly operation to search a node in N-ary tree. To improve search, we maintain a hash which keeps track of pointer of each node based on same key value. Whenever we want to delete a node, just take pointer from hash and delete it. Similarly, while insertion of a node also, use hash to locate parent pointer.
Update a child in N-ary tree
Using hash mentioned before, locate node pointer, update information by adding new node in children array of parent. Simple!
To print a N-ary tree in level order
No big deal here, it is same as binary search tree level order traversal. Use queue and for node visited, add all children of it on to queue. Take out next node from queue. Repeat process till queue is not empty. Level order traversal of N-ary tree implementation.
Above n-ary tree structure can be used to represent organizational structure where an employee can be CEO, MANAGER or EMPLOYEE. CEO is at the first level, MANAGER at the second layer and EMPLOYEE at last layer. Figure shows the layout of Nary tree for organizational tree:
So this is about N-ary tree, use it wherever you want to store hierarchical data.
Please share if there is something wrong or missing. If you are interested in contributing to website or have an interview experience to share, please contact us.