# Deleting a Node from an N-ary Tree

**In this tutorial you will learn how to delete a node from an N-ary tree. The video can be found here, where the implementation is done in C++. I will provide the pseudocode in the tutorial.**

An **n-ary tree** is a data structure in which each node can have any number of children (n). This is unlike binary trees where a node can have a maximum of 2 children. **A common example is representing employees in an organization, or a family tree**. A **node **is any object of the tree. Consider this 3-ary tree:

When deleting a node, there are **4 options** to look at, the node either:

Is a leaf node (has no children) - e.g. nodes 12, 1

Has only one child - e.g node 6 has only one child, 2

Has >1 child and we want to promote them all - e.g. node 7 has children 12, 1

Has >1 child and we want to promote only one of them - e.g. remove node 9 and promote 18

**What do I mean by options 3 and 4? **Consider deleting node 9, either nodes 11, 2 and 18 can be placed under node 5 (at the same level as nodes 7 or 6). The other option is to choose one of 11, 2 or 18 and place that in the position of 9. If we choose node 2 for instance, then 11 and 18 would become the children of 2, and node 2 will be in the position of 9 (next to 7 and 6). With this logic, it is imperative to also have a parent pointer of each node. That is, the user must be able to retrieve the parent of any node selected within the tree.

Another note, Options 2 and 3 above can actually be combined. However the implementation is slightly different in code form, that is why I broke it up separately.

The following is my recursive algorithm to search for a node in N-ary tree. The root is the head node. There is a global variable *foundNode *present so it does not get reset during each recursive call. **For this to work ****optimally ****each tree must have a ****unique node value****, **since it returns the left most node it finds matching the data.

function findNode(root, nodeToFind)

if (root is nodeToFind)

*foundNode* = root

return *foundNode*

else

for (i = 0 to number of children of root)

findNode(child[i], nodeToFind)

end

return *foundNode*

end

end function

To delete a node, it has to first be searched and returned as a node object, intuitively since we need all the children of that node and it's parent too.

### Algorithm to delete a node from n-ary tree

Here is the pseudocode, in this case I am calling findNode inside this function. Alternatively you can call it outside and pass that Node object in, depending on your specific implementation. The node to remove is nodeToRemove. The promoteSetting option contains the node to promote for option 4. **It MUST match the child of the node to fire or either be set to indicate all nodes.**

function deleteNode(root, nodeToRemove, promoteSetting)

*searchedNode *= findNode(root, nodeToRemove)

*sNparent *= parent of searchedNode

**//Case 1 (leaf node)**

if (searchedNode has 0 children)

delete *searchedNode*

**//Case 2 (one child only)**

else if (*searchedNode *has 1 child)

*oneChild *= child of *searchedNode*

for (i = 0 to number of children of *sNparent*)

if child[i] = nodeToRemove

child[i] = *oneChild*

end

end

set the parent of *oneChild *to *sNparent*

**//Case 3 (many children, promote all)**

* *else if (*searchedNode *has >1 child & promoteSetting* *= all)

*allChildren *= children of *searchedNode*

for (i = 0 to number of children of *sNparent*)

if child[i] = *nodeToRemove*

delete child[i]

end

end

for (i = 0 to size of *allChildren*)

parent of *allChildren*[i] = *sNparent*

append *allChildren*[i] to children of *sNparent*

end

**//Case 4 (many children, promote one)**

else

*allChildren *= children of searchedNode

for (i = 0 to size of *allChildren*)

if child[i] = promoteSetting

*nodeToPromote *= child[i]

set parent of *nodeToPromote *to *sNparent*

end

end

for (i = 0 to number of children of *sNparent*)

if child[i] = nodeToRemove

delete child[i]

*InsertPosition *= i

end

end

for (i = 0 to size of *allChildren*)

if child[i] is not promoteSetting

append child[i] to children of *nodeToPromote*

set parent of child[i] to *nodeToPromote** *

end

end

append *nodeToPromote *at *sNparent*[*InsertPosition*]

end

return root

end function

That's it for the algorithm! Thank you for reading

Vinayak