Public Class Form1
    Dim t As New Tree
    Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click

        'build the tree
        t.InsertNode("Harriet")
        t.InsertNode("Garry")
        t.InsertNode("Ronnie")
        t.InsertNode("Chrissy")
        t.InsertNode("Wendy")
        t.InsertNode("Paul")
        t.InsertNode("Donnie")
        t.InsertNode("Danny")

        t.PreorderTraversal()   'traverse the tree

        t.SearchTree("Paul")    'search the tree

    End Sub
End Class
Public Class Tree
    Dim root As TreeNode
    Public Sub InsertNode(ByVal NewValue As String)
        'used to build the tree
        If root Is Nothing Then
            root = New TreeNode(NewValue)
        Else
            root.Insert(NewValue)
        End If
    End Sub

    Dim stOut As String
    Public Sub InorderTraversal()
        'We need this method because need to be able to launch the recursive traversal
        'and pass it a tree's root node for the first invocation
        'but the button code cannot access the tree's node because it's private

        stOut = ""
        Call Inorder(root)
        MsgBox(stOut)
    End Sub
    Public Sub Inorder(ByVal node As TreeNode)
        If node.LeftNode IsNot Nothing Then
            Call Inorder(node.LeftNode)
        End If
        stOut = stOut & node.Data & " "
        If node.RightNode IsNot Nothing Then
            Call Inorder(node.RightNode)
        End If
    End Sub
    Public Sub PreorderTraversal()
        stOut = ""
        Call Preorder(root)
        MsgBox(stOut)
    End Sub
    Public Sub Preorder(ByVal node As TreeNode)
        stOut = stOut & node.Data & " "
        If node.LeftNode IsNot Nothing Then
            Call Preorder(node.LeftNode)
        End If
        If node.RightNode IsNot Nothing Then
            Call Preorder(node.RightNode)
        End If
    End Sub
    Public Sub PostorderTraversal()
        stOut = ""
        Call Postorder(root)
        MsgBox(stOut)
    End Sub
    Public Sub Postorder(ByVal node As TreeNode)
        If node.LeftNode IsNot Nothing Then
            Call Postorder(node.LeftNode)
        End If
        If node.RightNode IsNot Nothing Then
            Call Postorder(node.RightNode)
        End If
        stOut = stOut & node.Data & " "
    End Sub
    Public Sub SearchTree(target As String)
        Dim currentnode As TreeNode
        currentnode = Me.root
        Dim bNotFound As Boolean
        While currentnode.Data <> target And bNotFound = False
            If target < currentnode.Data Then
                If currentnode.LeftNode IsNot Nothing Then
                    currentnode = currentnode.LeftNode
                Else
                    bNotFound = True
                End If
            ElseIf target > currentnode.Data Then
                If currentnode.RightNode IsNot Nothing Then
                    currentnode = currentnode.RightNode
                Else
                    bNotFound = True
                End If
            End If
        End While
        If bNotFound = True Then
            MsgBox(target & " not found")
        Else
            MsgBox(target & " found")
        End If
    End Sub

End Class

Public Class TreeNode
    Public LeftNode As TreeNode         'each node could have a node at its left
    Public RightNode As TreeNode        'each node could have a node at its right
    Public Data As String               'each node carries some data

    Public Sub New(ByVal nodeData As String)    'when a new node is created
        Me.Data = nodeData                      'its data property is initialised
        Me.LeftNode = Nothing                   'its left child is set to Nothing
        Me.RightNode = Nothing                  'its right child is set to Nothing
    End Sub
    Public Sub Insert(ByVal NewValue As String)
        If NewValue < Me.Data Then
            If Me.LeftNode Is Nothing Then
                Me.LeftNode = New TreeNode(NewValue)
            Else
                Me.LeftNode.Insert(NewValue)
            End If
        ElseIf NewValue > Me.Data Then
            If Me.RightNode Is Nothing Then
                Me.RightNode = New TreeNode(NewValue)
            Else
                Me.RightNode.Insert(NewValue)
            End If
        End If
    End Sub

End Class