Const nullPtr As Integer = -1
Dim root As Integer
Dim freeListPtr As Integer

Structure TreeNode
    Public data As Integer
    Public left As Integer
    Public right As Integer
End Structure

Sub insertNode(ByRef tree() As TreeNode, data As Integer)
    Dim currentPtr, previousPtr, newNodePtr As Integer
    Dim turnedLeft As Boolean
    If freeListPtr <> nullPtr Then
        newNodePtr = freeListPtr
        freeListPtr = tree(freeListPtr).left
        tree(newNodePtr).data = data
        tree(newNodePtr).left = nullPtr
        tree(newNodePtr).right = nullPtr

        If root = nullPtr Then
            root = newNodePtr
        Else
            currentPtr = root
            While currentPtr <> nullPtr
                previousPtr = currentPtr
                If tree(currentPtr).data > data Then
                    turnedLeft = True
                    currentPtr = tree(currentPtr).left
                Else
                    turnedLeft = False
                    currentPtr = tree(currentPtr).right
                End If
            End While
            If turnedLeft Then
                tree(previousPtr).left = newNodePtr
            Else
                tree(previousPtr).right = newNodePtr
            End If
        End If
    Else
        Console.WriteLine("ERROR - Cannot insert node in full tree.")
    End If
End Sub

Sub dumpBinaryTree(tree() As TreeNode)
    'displays contents of variables
    Console.WriteLine(Environment.NewLine)
    Console.WriteLine("head ptr " & root)
    Console.WriteLine("free ptr " & freeListPtr)
    Console.WriteLine(Environment.NewLine)
    Console.WriteLine("LEFT  DATA  RIGHT")
    For Each node In tree
        Console.WriteLine(node.left & "     " & node.data & "     " & node.right)
    Next
    Console.WriteLine(Environment.NewLine)
End Sub

Sub Main()
    Dim bst() As TreeNode = newBinarySearchTree(4)

    Console.WriteLine("INITIAL CONTENTS OF BST")
    dumpBinaryTree(bst)

    insertNode(bst, 6)
    insertNode(bst, 9)
    insertNode(bst, 2)

    Console.WriteLine("FINAL CONTENTS")
    dumpBinaryTree(bst)
    Console.ReadLine()
End Sub

Function newBinarySearchTree(maxIndex As Integer) As TreeNode()
    If maxIndex < 1 Then
        Console.WriteLine("ERROR - Binary Search Tree max index cannot be less than 1.")
    End If
    root = nullPtr
    freeListPtr = 0
    Dim tree(maxIndex) As TreeNode
    For i = 0 To maxIndex - 1
        tree(i).left = i + 1
    Next
    tree(maxIndex).left = nullPtr
    Return tree
End Function

Function findNode(tree() As TreeNode, data As Integer) As Integer
    Dim currentPtr As Integer = root
    While currentPtr <> nullPtr And tree(currentPtr).data <> data
        If tree(currentPtr).data > data Then
            currentPtr = tree(currentPtr).left
        Else
            currentPtr = tree(currentPtr).right
        End If
    End While
    Return currentPtr
End Function

Function bstMin(tree() As TreeNode) As Integer
    If root = nullPtr Then : Return nullPtr : End If
    Dim previousPtr, currentPtr As Integer
    currentPtr = root
    While currentPtr <> nullPtr
        previousPtr = currentPtr
        currentPtr = tree(currentPtr).left
    End While
    Return tree(previousPtr).data
End Function

Function bstMax(tree() As TreeNode) As Integer
    If root = nullPtr Then : Return nullPtr : End If
    Dim previousPtr, currentPtr As Integer
    currentPtr = root
    While currentPtr <> nullPtr
        previousPtr = currentPtr
        currentPtr = tree(currentPtr).right
    End While
    Return tree(previousPtr).data
End Function