CODEWITHSUNDEEP
gobinary-search-tree
UnleashMe69
UnleashMe69

Reputation: 48

Delete function of a binary search tree does not delete leaf node

I am implementing a binary search tree in Go. So far, I managed to implement the following functions:

The only function I didn't manage to implement successfully yet is the delete function. When the node to be deleted is a leaf, it does not get deleted.

When I try to delete the node containing the value 8, I am expecting the following output:

{10 <nil> 0xc00009a060}
{12 <nil> <nil>}
{15 0xc00009a018 0xc00009a030}
{18 <nil> <nil>}
{20 0xc00009a078 0xc00009a090}
{25 <nil> <nil>}

However, I get the following output:

{8 <nil> <nil>}
{10 0xc00009a048 0xc00009a060}
{12 <nil> <nil>}
{15 0xc00009a018 0xc00009a030}
{18 <nil> <nil>}
{20 0xc00009a078 0xc00009a090}
{25 <nil> <nil>}

You can find my source code here: https://play.golang.org/p/oaCYEgCt-qI

Upvotes: 1

Views: 237

Answers (1)

Brits
Brits

Reputation: 18370

if value < tree.data {
    *parent = *tree
    tree = tree.left
} else if value > tree.data {
    *parent = *tree
    tree = tree.right
}

In this section *parent = *tree is taking a copy of the node. Later on you use parent.right = nil which amends the copy (not the node that is linked from above in the tree). So changing *parent = *tree to parent = tree resolves the issue (playground). Note that you also need to consider what should happen if the found node is the top of the tree (I have not addressed that case).

Upvotes: 1

Related Questions