Click here to Skip to main content
15,867,686 members
Articles / Programming Languages / Visual Basic

A simple binary tree implementation with VB.NET

Rate me:
Please Sign up or sign in to vote.
3.75/5 (21 votes)
29 Jul 2003CPOL4 min read 254.6K   3.5K   59   20
This article gives a very simple implementation of the binary tree data structure using VB.NET

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.

A binary tree

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:

VB.NET
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.

VB.NET
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.

VB.NET
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:

VB.NET
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!

VB.NET
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:

sorted list

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!

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Web Developer
India India
I am a software developer and have worked on Microsoft technologies for about five years now. I have always been fascinated by Microsoft technologies and with the advent of .NET , this fascination has reached new heights. I take a lot of interest reading technical articles and equally enjoy writing them. I really like to be called a .NET junkie and will surely try to live up to this name Smile | :)

I am .NET MVP and have also completed MCAD, MCSD(VS 6), MCDBA (SQL Server 2000), MCSA (Win 2K) and MCTS (Distributed Apps) certfications.

Comments and Discussions

 
Generali need help [modified] Pin
ramadp4-Oct-10 5:19
ramadp4-Oct-10 5:19 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.