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:

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

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

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

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