A simple binary tree implementation with VB.NET

• Download source files - 5.59 Kb

Introduction

Binary tree is one of the most important data structures in the programming world. The basic definition can be given as follows (as mentioned in one of the data structures book by Tenenbaum). "A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called root of the tree. The other two subsets are themselves binary trees, called left and right sub trees of the original tree. A left or right sub tree can be empty and each element off the binary tree is called as the node." The definition itself is recursive in nature and might sound cryptic. This diagram would make this more clear.

There are countless variations to the basic the Binary tree defined and each of these have various applications. For example, the Heap is an implementation of the binary tree. Various low level data structures of the file system and databases would be a heap. This list just goes on...

Implementing a binary tree

In this article we shall see a very simple binary tree implementation. In terms of implementation, a binary tree is a type of a linked list of nodes. So, let's see how a node can be defined:

    Class TreeNode
        Public Value As Object
        Public LeftNode As TreeNode
        Public RightNode As TreeNode
    End Class

Here, I have a class called TreeNode with members LeftNode and RightNode to point to a left and right sub tree respectively, and Value which is type Object (can hold anything). I really would have liked a structure to represent a node instead of a class (like in those C days), but in VB.NET, a structure cannot contain a member of its own type.

Creating a tree itself, again, is pretty simple. First, you create the root and then create the right and left sub trees. In our example, we create a simple tree of integers generated randomly. Let's see how this is done.

We represent the Tree as a class which exposes several methods to operate on it. Note that the root of the tree is made private and the only way to operate on the tree is through methods exposed by the Tree class.

Public Class Tree
    Private _root As TreeNode
    
    ..
    ..
End Class
        

To create a new tree, we create a new node in the class constructor and mark it as the root.

Sub New(ByVal rootValue As Object)
   _root = GetNode(rootValue)
End Sub

Private Function GetNode(ByVal value As Object) As TreeNode
    Dim node As New TreeNode()
    node.Value = value
    Return node
End Function
        

Adding nodes to the tree

Adding a node to a tree is a bit more involved effort as a node can fit in one and only one place in a tree after a root is in place. We need to start with the root and compare the value of the root with the node's value. If the node value is smaller, then it goes to left sub tree and if it is greater, then it forms a part of the right sub tree. These comparisons happen all the way to the bottom of the tree, where we cannot proceed any further. At this point, one final comparison is made and the node is added to the final node's left or right sub tree. In my implementation, I dont support duplicate nodes. If in the process of adding a node, if its value is equal to node being compared, it is not added to the tree. Here's the code snippet:

Public Sub AddtoTree(ByVal value As Object)
    Dim currentNode As TreeNode = _root
    Dim nextNode As TreeNode = _root

    While currentNode.Value <> value And Not nextNode Is Nothing
        currentNode = nextNode
        If nextNode.Value < value Then
            nextNode = nextNode.RightNode
        Else
            nextNode = nextNode.LeftNode
        End If
    End While
    If currentNode.Value = value Then
        Console.WriteLine("Duplicate value (" & _
             value & "). Node was not inserted")
    ElseIf currentNode.Value < value Then
        currentNode.RightNode = GetNode(value)
    Else
        currentNode.LeftNode = GetNode(value)
    End If
End Sub
        

Note that in the above sample, I am making comparisons directly on the node value itself. This is under the assumption that all my nodes represent simple integers. Ideally, we should have a Key for each node and the comparisons should happen on this field. In terms of implementation, this Key object should implement IComparable interface so that the tree can be of any type of object (the comparison would be transparent).

Traversing the tree

Traversing a tree involves visiting all the nodes in the tree. There are three ways you can achieve this:

• Post Order Traversal
• Pre Order Traversal
• In Order Traversal

Each of these approaches is very useful and has its own applications. In our sample, we shall consider Inorder traversal. This is a recursive process as explained below:

1. Traverse the left sub tree
2. Visit the root
3. Traverse the right subtree

The significance of this traversal is that we visit all the nodes in a sorted fashion. So, in our case, we shall obtain the sorted list of integers by just traversing in order!

Private Sub inOrderTraverse(ByVal node As TreeNode)
    If Not node Is Nothing Then
        inOrderTraverse(node.LeftNode)
        Console.WriteLine(node.Value)
        inOrderTraverse(node.RightNode)
    End If
End Sub
            

Here's a sample output:

Conclusion

In this article, we saw how a simple binary tree could be implemented with ease using VB.NET. Guys from the C world would notice that malloc,sizeof and free were not used used here. This is because I have left it to the .NET runtime to worry about allocation and collection (that's the best part)

I kept this article very simple by not considering more involved operations like Delete and Enumeration. Also, the very notion of Binary tree opens countless avenues in terms of algorithms and implementations. I would really like to write many articles involving these algorithms in the near future!