I can't trace the mistake in my logic in BST delete function in Go.
func delete(d *Node, v int) {
if d == nil {
fmt.Println("The tree is empty")
}
if v < d.key {
delete(d.left, v)
} else if v > d.key {
delete(d.right, v)
} else if v == d.key {
if d.right == nil && d.left == nil {
d = nil
} else {
if d.left == nil && d.right != nil {
d.key= d.right.key
delete(d.right,d.key)
} else if d.right == nil && d.left != nil {
d.key= d.left.key
delete(d.left,d.key)
}else{
min := minvalue(d.right)
d.key = min.key
delete(d.right, min.key)
}
}
}
}
The output shouldn't contain 4 but the result is instead showing 6 two times
The expected output is 5 6, but it's showing 4 6 6
As several have noted in the comments, you should provide a Minimal Reproducible Example, which helps people avoid wasting time on simple misunderstandings.
In this case, though, it's pretty obvious what you have done wrong—at least, at the first layer. (There may be more, depending on what you intend to do with these trees.)
Consider the following function:
func setToNil(p *int) {
p = nil
}
Let's use this from a main:
func main() {
x := 3
px := &x
fmt.Println("before: x =", x, "px =", px)
setToNil(px)
fmt.Println("after: x =", x, "px =", px)
}
(Complete version on the Go playground)
What do you expect this program to do? Try it out: did it do what you expected? Why, or why not? If not, what about this variant:
func setToTheAnswer(i int) {
i = 42
}
func main() {
x := 3
fmt.Println("before: x =", x)
setToTheAnswer(x)
fmt.Println("after: x =", x)
}
Fill in the rest and try it out. Why didn't x change? (Should it have changed? If you think so, why do you think so? The language definition says that it should not.)
Now, compare that to this version:
func setToTheAnswer(p *int) {
*p = 42
}
func setToNil(q **int) {
*q = nil
}
func main() {
x := 3
px := &x
fmt.Println("before: x =", x, "px =", px)
setToTheAnswer(px)
setToNil(&px) // note the & in front of px
fmt.Println("after: x =", x, "px =", px)
}
What will this version do? Try it on the playground.
dYour function:
func delete(d *Node, v int) {
// ...
}
takes a parameter named d of type pointer to Node (and v of type int of course). If you change d in delete, that has no effect on any * Node variable in any caller, because d is a copy of this pointer-to-Node. You can change *d to change the Node to which the caller's pointer points, but you cannot change the caller's pointer.
There are multiple different ways to fix this. For instance, instead of taking a d *Node you might take a different object that contains a root *Node pointer, or you might take a pd **Node so that you can update a d *Node in the caller. Which is the right way? That's up to you.