Search code examples
algorithmternary-tree

How to delete a node in Ternary Tree?

I am working on implementing a Java program on inserting and deleting a node in a ternary tree.

I am able to implement insertion without any issues, but I'm facing a few hiccups in implementing the deletion operation.

So, my question is:

How to delete a node from ternary tree if it has one or more child nodes?

It will be great if you can share any logic or pseudo-code to implement the "delete" functionality.

Solution

  • I found a solution.

    Suppose n is the node we want to delete, l is its left child, r is its right child and m is its middle child.

    • If n is a root node, then make n null.

    • If n is not a root node, then check if m is not null. If so, simply invoke recursively the current procedure on m, since m matches n in value: we will delete the last matching node!

    • If m is null, then we have the following possible cases:

      • If both l and r are null, then make l, r and m values in the parent node n to be null.

      • If only one node, say x, (either l or r) is not null, then replace x non-null value with n's value, and delete x.

      • If both l and r are not null, then find the node z with maximum value in the left sub-tree of n, and replace z's value to with n's node, and delete z.