PM Task 2 2021 beta v1.0

    Structure treeNode
        Public data As String
        Public left As Integer
        Public right As Integer
    End Structure
    ReadOnly nullPtr As Integer = -1
    Class ColorTree
        Dim head As Integer
        Dim freeNodePtr As Integer
        Dim tree() As treeNode
        Sub New(maxIndex As Integer)
            ReDim tree(maxIndex)
            head = -1
            freeNodePtr = 0
            For i = 0 To maxIndex
                tree(i).left = i + 1
                tree(i).right = nullPtr
            Next
            tree(maxIndex).left = nullPtr
        End Sub
        Sub addColor(color As String)
            If freeNodePtr = -1 Then
                Console.WriteLine("Error: Color tree is full!")
                Exit Sub
            End If
            Dim newNodePtr = freeNodePtr
            freeNodePtr = tree(freeNodePtr).left

            tree(newNodePtr).data = color
            tree(newNodePtr).left = nullPtr
            tree(newNodePtr).right = nullPtr

            Dim prevNodePtr, currNodePtr As Integer
            Dim turnedLeft As Boolean
            currNodePtr = head
            While currNodePtr <> nullPtr
                prevNodePtr = currNodePtr
                If color < tree(currNodePtr).data Then
                    currNodePtr = tree(currNodePtr).left
                    turnedLeft = True
                Else
                    currNodePtr = tree(currNodePtr).right
                    turnedLeft = False
                End If
            End While
            If head = nullPtr Then
                head = newNodePtr
            Else
                If turnedLeft Then
                    tree(prevNodePtr).left = newNodePtr
                Else
                    tree(prevNodePtr).right = newNodePtr
                End If
            End If

        End Sub

    End Class