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 maken
null
.If
n
is not a root node, then check ifm
is notnull
. If so, simply invoke recursively the current procedure onm
, sincem
matchesn
in value: we will delete the last matching node!If
m
isnull
, then we have the following possible cases:If both
l
andr
arenull
, then makel
,r
andm
values in the parent noden
to benull
.If only one node, say
x
, (eitherl
orr
) is notnull
, then replacex
non-null value withn
's value, and deletex
.If both
l
andr
are notnull
, then find the nodez
with maximum value in the left sub-tree ofn
, and replacez
's value to withn
's node, and deletez
.