13,196,946 members (58,203 online)
Add your own
alternative version

#### Stats

197.4K views
2.9K downloads
58 bookmarked
Posted 29 Jul 2003

# A simple binary tree implementation with VB.NET

, 29 Jul 2003
 Rate this:
Please Sign up or sign in to vote.
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.

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!

## License

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

## About the Author

 Web Developer 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

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

 View All Threads First Prev Next
 a problem rahatshinwari8931-Dec-08 20:35 rahatshinwari89 31-Dec-08 20:35
 Last Visit: 31-Dec-99 18:00     Last Update: 20-Oct-17 9:06 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.171019.1 | Last Updated 30 Jul 2003
Article Copyright 2003 by Manoj G
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid