[tjoney]

I have coded a BTree and my delete method only deletes the last two numbers inorder. When it tries to delete any other node it doesn't and when it tries to delete the left child of the root and the root itself I get a stack overflow error.

 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

[tjoney]

Wow. Almost a week and no response. Not trying to be mean ( or even wanting to ) but if this question got posted in a C++ or Java forum I would have received help the first day. Do any VB.Net programmers even know how to do a B-Tree? Or should I stick with a different language. I really like the smoothness of the actual code and how clean it looks, and I would like to stick with VB.Net.

[AdamSpeight2008]

Maybe because you don't provide sufficient information.
- Have tried using even basic Debugging Skills?

- Provided no examples of the tree you start with, what you expect to get, what you actually got.

- "get a stack overflow error."
When the Exception is thrown its include a lot more information, like where it was throw.
A Stack Overflow is often the result of infinite recursion.

- Lack of comments in the code.

[tjoney]

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

There is whole program. I have commented what I was hoping to accomplish with my delete method and I have also commented where the stack overflow occurs. It occurs in the traversal call after what looks like the root has been deleted.

P.S. Sorry for my attitude yesterday, it was a really bad day.

[AdamSpeight2008]

The Stack Overflow is properly cause by loop in the nodes, where it occurs it don't know.

[tjoney]

So I finally got it to work. yeah!

Module Btree
    Public Class BTree
        Public root As Node

        Public Sub New()
            root = Nothing
        End Sub

        Public Sub Clear()
            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
                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 Boolean
            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
            While (True)
                Console.WriteLine(key & " is in the tree.")
                Exit While
            End While
            Return True
        End Function

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

        Public Function getSuccessor(ByVal dNode As Node) As Node
            Dim sParent As Node = dNode
            Dim successor As Node = dNode
            Dim current As Node = dNode.rightNode
            While (Not (current Is Nothing))
                sParent = successor
                successor = current
                current = current.leftNode
            End While
            If (Not (successor Is dNode.rightNode)) Then
                sParent.leftNode = successor.rightNode
                successor.rightNode = dNode.rightNode
            End If
            Return successor
        End Function

        Public Sub inOrder(ByVal theRoot As Node)
            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 parent 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)
        nums.Insert(555)


        Console.WriteLine("Inorder Traversal: " & vbCrLf)
        nums.inOrder(nums.root)

        nums.Delete(555)

        Console.Write(vbCrLf)

        nums.inOrder(nums.root)
        Console.Write(vbCrLf)
        nums.Contains(37)
        nums.Clear()

        nums.inOrder(nums.root)

        Console.Write("Press enter to continue. ")
        Console.ReadLine()
    End Sub

End Module