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