A Very Basic Non-Recursive Binary Search Tree For Excel VBA

• Download source code - 33.7 KB

Introduction

A little while ago, I was authoring a VBA script that cycled over thousands of lines of values (integers) and I was putting these values into an array. If you, the reader, are familiar with VBA and arrays, this is an easy task and VBA does it well. Now here came my issues: Firstly, I had to compare different sets of values from one row of the array to the next. This was accomplished by creating new arrays. Secondly, the newly created arrays took a long time to figure out all the details. This is where a stack, queue, and linked list would have worked well and I found all of those code snippets with little online searching and adapted them to my needs. Then I thought, "What about a binary search tree?" I have used them plenty of times in other languages such as C# and C++. So I started more online research and quickly found a few .NET examples and several ways to call code other than VBA into my macro to make a binary search tree (BST) but I wanted to use native VBA. Using VBA only means that my Excel workbook should function across a large array of different computers with different versions of Excel. In my short experience, many businesses both large and small use Excel and utilizing VBA means custom scripts in an environment that does not support custom programs written in other languages. And in my research, I found one example of a BST using only VBA that I could not make function. This is my version of a BST using VBA.

Background

A BST is an abstract data type that uses nodes (integer, child left, child right) to store and view data based upon values. In my example, I am excluding a Key and using integers only for my values. The first node is the root and this is the starting value for the tree and the link to the left and right child. After the root is set, the next value is either equal to or less than the root for the left child or greater than the root for the right child. A new node is added at the correct location with the value and a link to a new left or right child. This process continues until all the values are added to the tree. I am allowing duplicates to keep the algorithm simple and Nothing is almost equivalent to Null. There are many sources on how BSTs work, so feel free to explore them!

Using the Code

This is a simple BST that is implemented with two class modules and a main testing module. The BST random example has features such as search, insert, delete, and traversal. Download the example for full explanation of the function or go to this article's sister article.

Here is the "TreeNode" class with a variant to hold the integer value and left and right TreeNodes to link to the next node. Again, this is a basic BST so a Key holder is not included.

Option Explicit
' stores the count of how many of each value is present
Public ValueCount As Long
' stores the actual value (integer in this case)
Public Value As Variant
' stores the pointer to the left child node
Public LeftChild As TreeNode
' stores the pointer to the right child node
Public RightChild As TreeNode

Here is the "BinarySearchTree" class that contains all the definitions, scripts, and functions in order to manipulate the BST.

 ' always force declaration of variables
Option Explicit
' access to the insert function and pass in value without recursion
Public Function insert(TN As TreeNode, valToInsert As Variant) As TreeNode
    If TN Is Nothing Then
        Set TN = getNewNode(valToInsert)
    Else
        Dim tempNode As TreeNode
        Dim newNode As TreeNode
        Set newNode = TN
        ' loop until Nothing if found in tree (left or right)
        Do While Not newNode Is Nothing
            Set tempNode = newNode
            ' check for duplicates
            If valToInsert = newNode.Value Then
                newNode.ValueCount = newNode.ValueCount + 1: Exit Do
            ' go left of right based upon value
            ElseIf valToInsert < newNode.Value Then
                Set newNode = newNode.LeftChild
            ElseIf valToInsert > newNode.Value Then
                Set newNode = newNode.RightChild
            End If
        Loop
        ' get a new node
        If valToInsert < tempNode.Value Then
            Set tempNode.LeftChild = getNewNode(valToInsert)
        ElseIf valToInsert > tempNode.Value Then
            Set tempNode.RightChild = getNewNode(valToInsert)
        End If
    End If
    Set insert = TN
End Function
' basic add function
Private Function getNewNode(v As Variant) As TreeNode
    Set getNewNode = New TreeNode
    getNewNode.Value = v
    getNewNode.ValueCount = 1
End Function

If you notice, the private function getNewNode() to set the root and is separate from the insert function. This is simply to make the process easier for me to understand and these two could easily be integrated into the insert function.

Points of Interest

This was a test of my patience to get the nodes to work. I made a linked list easily enough, but the left and right nodes eluded me for some time. I was trying to use recursion for the add function based off of a C++ code snippet and this website. For some reason, the pointer to the child node kept referring to a new node instead of the last child node. For the solution, I adapted Manoj's VB.NET add function that did not use recursion and viola! Problem solved. His original code is located here.

History

• 17^th February, 2019 v1.0.0: Initial release
• 19^th February, 2019: Removed <code> artifacts
• 23^rd February, 2019: Added link to sister article
• 24^th February, 2019: Updated download and classes