I am implementing node deletion in binary search tree. I have implemented a method which look good (at algorithm standpoint). But do not work. After spending hours trying to understand why, I would love to get some help from you.
BST definition
type Node struct {
Data int
Left *Node
Right *Node
}
Helper methods (they have been tested and works)
// New returns a pointer to a mew node (like the new construct in Go)
func New(data int) *Node {
return &Node{Data: data}
}
// Find checks whether some data exist in the bst and returns the corresponding node
func (bst *Node) Find(data int) *Node {
if bst == nil {
return bst
}
if bst.Data == data {
return bst
}
if data < bst.Data {
return bst.Left.Find(data)
}
return bst.Right.Find(data)
}
// Min returns the smallest element in a bst
func (bst *Node) Min() *Node {
if bst == nil {
return nil
}
current := bst
for current.Left != nil {
current = current.Left
}
return current
}
The non working method
// Delete removes a key from the binary tree
func (bst *Node) Delete(data int) *Node {
if bst == nil {
return bst
}
current := bst
toDelete := current.Find(data)
if toDelete == nil {
return current
}
if toDelete.Right == nil && toDelete.Left != nil {
toDelete = toDelete.Left
return current
}
if toDelete.Right != nil && toDelete.Left == nil {
toDelete = toDelete.Right
return current
}
inOrderSuccessor := toDelete.Right.Min()
toDelete = inOrderSuccessor
return current
}
Test
func main() {
root := bst.New(8)
root.Left = bst.New(3)
root.Right = bst.New(10)
root.Left.Left = bst.New(1)
root.Left.Right = bst.New(6)
fmt.Println(root.InOrder())
root = root.Delete(3)
fmt.Println(root.InOrder())
}
output
1->3->6->8->10->
1->3->6->8->10->
There is something wrong in the Delete method but I could not understand why.
This code can be run in the playground here https://go.dev/play/p/oJZMOCp2BXL
