Binary search tree delete method

[T.j. Oney]

I have a delete method for a binary search tree. It only deletes the last two entered values. When trying to delete the root or anything to left of it it returns a null pointer exception.


Public Function Delete(ByVal key As Integer) As Boolean
Dim current As Node = root
Dim parent As Node = root
Dim isLeftChild As Boolean = True
While (current.value <> key)
parent = current
If (key < current.value) Then
isLeftChild = True
current = current.rightNode
Else
isLeftChild = False
current = current.rightNode
End If
If (current Is Nothing) Then
Return False
End If
End While
If (current.leftNode Is Nothing And current.rightNode Is Nothing) Then
If (current Is root) Then
root = Nothing
ElseIf (isLeftChild) Then
parent.leftNode = Nothing
Else
parent.rightNode = Nothing
End If
ElseIf (current.rightNode Is Nothing) Then
If (current Is root) Then
root = current.leftNode
ElseIf (isLeftChild) Then
parent.leftNode = current.leftNode
Else
parent.rightNode = current.rightNode
End If
ElseIf (current.leftNode Is Nothing) Then
If (current Is root) Then
root = current.rightNode
ElseIf (isLeftChild) Then
parent.leftNode = parent.rightNode
Else
parent.rightNode = current.rightNode
End If
Else
Dim successor As Node = getSuccessor(current)
If (current Is root) Then
parent.leftNode = successor
Else
parent.rightNode = successor
End If
successor.leftNode = current.leftNode
End If
Return True
End Function


Thanks in advance for the help

 

[jmcilhinney]

Syntax colouring is all well and good but your code is too hard to read without formatting. Please wrap your code snippets in

 tags to retain indenting, which makes it far more readable.

 

[T.j. Oney]

Module Module1
    Public Class BTree
        Public root As Node
        Public Sub New()
            root = Nothing
        End Sub
        Public Sub Insert(ByRef i As Integer)
            Dim newNode As New Node()
            newNode.value = i
            If (root Is Nothing) Then
                root = newNode
            Else
                Dim current As Node = root
                Dim parent As Node
                While (True)
                    parent = current
                    If (i < current.value) Then
                        current = current.leftNode
                        If (current Is Nothing) Then
                            parent.leftNode = newNode
                            Exit While
                        End If
                    Else
                        current = current.rightNode
                        If (current Is Nothing) Then
                            parent.rightNode = newNode
                            Exit While
                        End If
                    End If
                End While
            End If
        End Sub
        Public Function Contains(ByVal key As Integer) As Node
            Dim current As Node = root
            While (current.value <> key)
                If (key < current.value) Then
                    current = current.leftNode
                Else
                    current = current.rightNode
                End If
                If (current Is Nothing) Then
                    Return Nothing
                End If
            End While
            Return current
        End Function
        Public Function Delete(ByVal key As Integer) As Boolean
            Dim current As Node = root
            Dim parent As Node = root
            Dim isLeftChild As Boolean = True
            While (current.value <> key) ' go to the node to be deleted
                parent = current
                If (key < current.value) Then
                    isLeftChild = True
                    current = current.leftNode
                Else
                    isLeftChild = False
                    current = current.rightNode
                End If
                If (current Is Nothing) Then
                    Return False
                End If
            End While
            If (current.leftNode Is Nothing And current.rightNode Is Nothing) Then ' test if it is a leaf
                If (current Is root) Then
                    root = Nothing
                ElseIf (isLeftChild) Then
                    parent.leftNode = Nothing
                Else
                    parent.rightNode = Nothing
                End If
            ElseIf (current.rightNode Is Nothing) Then ' test if there is a left child
                If (current Is root) Then
                    root = current.leftNode
                ElseIf (isLeftChild) Then
                    parent.leftNode = current.leftNode
                Else
                    parent.rightNode = current.rightNode
                End If
            ElseIf (current.leftNode Is Nothing) Then ' test if there is right child
                If (current Is root) Then
                    root = current.rightNode
                ElseIf (isLeftChild) Then
                    parent.leftNode = parent.rightNode
                Else
                    parent.rightNode = current.rightNode
                End If
            Else
                Dim successor As Node = getSuccessor(current) ' test if there are two children
                If (current Is root) Then
                    parent.leftNode = successor
                Else
                    parent.rightNode = successor
                End If
                successor.leftNode = current.leftNode
            End If
            Return True
        End Function
        Public Function getSuccessor(ByVal dNode As Node) As Node ' gets successor for two child node
            Dim successorParent As Node = dNode
            Dim successor As Node = dNode
            Dim current As Node = dNode.rightNode
            While (Not (current Is Nothing))
                successorParent = successor
                successor = current
                current = current.leftNode
            End While
            If (Not (successor Is dNode.rightNode)) Then
                successorParent.leftNode = successor.rightNode
                successor.rightNode = dNode.rightNode
            End If
            Return successor
        End Function
        Public Sub inOrder(ByVal theRoot As Node) ' after deleting 24 this is where the stack overflow exception occurs. When I set
            ' a breakpoint it looks like infinte looping is going on here
            If (Not (theRoot Is Nothing)) Then
                inOrder(theRoot.leftNode)
                theRoot.displayNode()
                inOrder(theRoot.rightNode)
            End If
        End Sub
    End Class
    Public Class Node
        Public value As Integer
        Public leftNode As Node
        Public rightNode As Node
        Public Sub displayNode()
            Console.Write(value & " ")
        End Sub
    End Class
    Sub Main()
        Dim nums As New BTree()
        nums.Insert(24)
        nums.Insert(45)
        nums.Insert(16)
        nums.Insert(37)
        nums.Insert(3)
        nums.Insert(99)
        nums.Insert(22)
        Console.WriteLine("Inorder Traversal: " & vbCrLf)
        nums.inOrder(nums.root)
        nums.Delete(24)
        Console.Write(vbCrLf)
        nums.inOrder(nums.root)
        Console.Write("Press enter to continue. ")
        Console.ReadLine()
    End Sub
End Module

So I wrapped code tags around it and the indenting is not preserved. I have also included the whole program I wrote. The stack overflow exception occurs in the traversal call when the number 24 gets deleted from the tree.

 

[JohnH]

I just copy code from VS into forum editor and wrap code tags around it before or after pasting, no mangled formatting appear. You may have to go through the editor settings in your forum profile, it could be some setting there, though I can't see which. If you can't figure out how to post readable code you could paste the code into Notepad and attach the plain text file.