A Very Basic Recursive Binary Search Tree For Excel VBA

• Download source code - 36.8 KB

Introduction

I recently asked myself "What about a binary search tree in VBA?" I have used them plenty of times in other languages such as C# and C++ and they worked well so why can't I find many examples online for VBA?  I researched some more online 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. In my research, I found one example at Implementing a Binary Tree of a BST using only VBA that I finally made function with some modifications.  It seems that a lot of programmers would just as soon avoid VBA while I see it as a challenge, albeit one of tenacity with little to no rewards.

Background

According to this link, the definition of a BST is as follows: "Binary searchtree is a data structure that quickly allows us to maintain a sorted list of numbers

• It is called a binary tree because each node has maximum of two children.
• It is called a search tree because it can be used to search for the presence of a number in O(log(n)) time.

The properties that separate a binary search tree from a regular binary tree is [sic]

1. All nodes of left subtree are less than root node
2. All nodes of right subtree are more than root node
3. Both subtrees of each node are also BSTs, i.e., they have the above two properties"

This is just one definition of a BST. I have found many in my research and have decided on this basic definition with one more condition:

      4.  There should not be any duplicates in the BST.

To solve this problem, I am counting the duplicates, but another solution would be to skip them. I chose to count them because in an application for a BST, I might have to push the duplicates into linked lists if their key values are different, say in a dictionary application. 

Here is a picture of a binary tree from this link to help illustrate the data structure.

Here, we see the root equal to 9 and all the left subtrees are less than the previous node while all the right subtrees are greater than the previous node. Notice that in order for this picture to be a true BST that no node to the left has a higher value that the previous node and the opposite is true for the right nodes. Now swap in the number 2 for the number 5 in the diagram and it no longer is a BST even though 2 is less than 6.

Using the Code

This is a simple unbalanced BST that is implemented with two class modules (TreeNode and BinarySearchTree) and a Random_Main testing module, which contains the macro to run all the BST functions. The example fills a BST with 10 random integers and completes several functions:

• Insert
• In order traversal
• Pre order traversal
• Post order traversal
• Search (both pre and post delete)
• Delete
• Minimum value
• Maximum value
• Root value (both pre and post delete)

The Random_Main Module

The full example is available for downloading and all modules contain notes on each step of the process. Here is a portion of the "Random_MAIN" sub of the "Random_Main" module. This sub automatically picks random numbers, drives all the BST attributes, tracks the TreeNode, and prints out results to the Excel workbook main page (BST) and also to the immediate watch window. Open the code panel in the downloadable example and change bstSize to a value that represents how many BST values you want to automatically insert.  upperRnd is the highest value to enter while lowerRnd is the lowest value to enter and both of these can be changed as well. This is just to illustrate how the TreeNode and BinarySearchTree classes work and can be modified to suit many needs or can be created by the architect for her/his own needs.

' always force declaration of variables
Option Explicit
' change bstSize as suited for more or less vars in bst and upper or lower to extend value range in BST
Private Const bstSize As Integer = 10: Private Const upperRnd As Integer = 10, lowerRnd As Integer = 1
' declare WB, WS, and outPut as public to use in updating functions
Public WB As Workbook: Public WS As Worksheet: Public outPut As Collection
' this is our testing module to test the random bst
Public Sub Random_MAIN()
    ' turn off screen updating
    Application.ScreenUpdating = False
    ' local variables to use and declare a new BST and root
    Dim loopCount, rndNumber As Integer: Dim BST As New BinarySearchTree: Dim root As TreeNode
    ' set workbook, worksheet, and collection
    Set WB = ThisWorkbook: Set WS = WB.Sheets("BST"): Set outPut = New Collection
    ' loop x times and add random number
    For loopCount = 1 To bstSize
        rndNumber = rndOmizer: Set root = BST.insert(root, rndNumber): outPut.add (rndNumber)
    Next loopCount
    ' print out the input results and update BST sheet
    updateBSTSheet ("A"):  myPrint ("Order in which values are inserted."): myPrint ("")

The TreeNode Class Module

Here is the "TreeNode" class module with a variable to hold a value (Value) in the TreeNode, a variable to count duplicates (ValueCount), and links to the left and right child nodes (LeftChild and RightChild). Everything is declared Public for easy access outside the class.

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

The BinarySearchTree Class Module

Here is the "insert" function of the "BinarySearchTree" class module. This function creates the root TreeNode if it doesn't yet exist, adds a ValueCount to existing values instead of allowing duplicates, and recursively goes down to the first left or right Nothing TreeNode to add a new TreeNode then returns a TreeNode.

' public function to recursively insert value with no duplicates
Public Function insert(TN As TreeNode, valToInsert As Variant) As TreeNode
    ' create node if it doesn't exist
    If TN Is Nothing Then
        Set TN = New TreeNode
        TN.Value = valToInsert
        TN.ValueCount = 1
    ' count duplicates without expanding tree
    ElseIf TN.Value = valToInsert Then
        TN.ValueCount = TN.ValueCount + 1
    ' recursively call until empty node is found
    Else
        ' go left or right based on value and recursively call
        If valToInsert < TN.Value Then
            Set TN.LeftChild = insert(TN.LeftChild, valToInsert)
        ElseIf valToInsert > TN.Value Then
            Set TN.RightChild = insert(TN.RightChild, valToInsert)
        End If
    End If
    ' set the function to the node continually
    Set insert = TN
End Function

Here is the "delete" function of the "BinarySearchTree" class module. This function recursively deletes a TreeNode based upon Value, whether that TreeNode is a leaf, has no children, or is a binary tree and then returns a TreeNode. 

' public function to delete the value (node)
Public Function delete(TN As TreeNode, valToDelete As Variant) As TreeNode
    ' go left or right by value to be deleted and reccrsively call
    If valToDelete < TN.Value Then
        Set TN.LeftChild = delete(TN.LeftChild, valToDelete)
    ElseIf valToDelete > TN.Value Then
        Set TN.RightChild = delete(TN.RightChild, valToDelete)
    ' delete node if value is the same
    Else
        Dim copyNode As TreeNode
        ' node has no or only one child
        If TN.LeftChild Is Nothing Then
            Set copyNode = TN.RightChild: Set TN = Nothing: Set delete = copyNode: Exit Function
        ElseIf TN.RightChild Is Nothing Then
            Set copyNode = TN.LeftChild: Set TN = Nothing: Set delete = copyNode: Exit Function
        Else
        ' node has two children: 1st get inorder successor: 
        ' 2nd copy to this node: 3rd delete inorder successor
            Set copyNode = minValueNode(TN.RightChild): TN.Value = copyNode.Value: _
                           Set TN.RightChild = delete(TN.RightChild, copyNode.Value)
        End If
    End If
    ' set the function to the node continually
    Set delete = TN
End Function

Here is the "minValueNode" function of the "BinarySearchTree" class module. This function loops to find the successor TreeNode to the TreeNode that has two children and is being deleted, then returns a TreeNode. This function is called by the "delete" function.

' private function to find node's inorder successor
Private Function minValueNode(TN As TreeNode) As TreeNode
    ' loop down to find the leftmost leaf
    Dim tempNode As TreeNode: Set tempNode = TN
    While Not tempNode.LeftChild Is Nothing
        Set tempNode = tempNode.LeftChild
    Wend
    Set minValueNode = tempNode
End Function

Here is the "search" function of the "BinarySearchTree" class module. This function recursively finds the Value then returns a boolean.

' public function to search for a value
Public Function search(TN As TreeNode, valToSearch As Variant) As Boolean
    Dim searchNode As TreeNode: Set searchNode = TN
    ' loop until value is found (true) or bst ends (false)
    While Not searchNode Is Nothing
        If searchNode.Value = valToSearch Then
            search = True: Exit Function
        ElseIf valToSearch < searchNode.Value Then
            Set searchNode = searchNode.LeftChild
        Else
            Set searchNode = searchNode.RightChild
        End If
    Wend
End Function

Here is the "maxValue" function of the "BinarySearchTree" class module. This function loops right to find the maximum Value, then returns a Variant.

' public function to get the max value from right tree recursively
Public Function maxValue(TN As TreeNode) As Variant
    Dim maxValueNode As TreeNode: Set maxValueNode = TN
    While Not maxValueNode.RightChild Is Nothing
        Set maxValueNode = maxValueNode.RightChild
    Wend
    maxValue = maxValueNode.Value
End Function

Here is the "minValue" function of the "BinarySearchTree" class module. This function loops left to find the minmum Value then returns a Variant.

' public function to get the min value from left tree recursively
Public Function minValue(TN As TreeNode) As Variant
    Dim minValueNode As TreeNode: Set minValueNode = TN
    While Not minValueNode.LeftChild Is Nothing
        Set minValueNode = minValueNode.LeftChild
    Wend
    minValue = minValueNode.Value
End Function

Here is the "InOrder" function of the "BinarySearchTree" class module. This function recurves the BST in the order of the left TreeNode, then the root TreeNode, then the right TreeNode in order to display the values from smallest to largest. A Collection is returned but that variable could be an Array.

' public function to display the values in order from lowest to highest (left, root, right) recursively
Public Function InOrder(TN As TreeNode, Optional myCol As Collection) As Collection
    If Not TN Is Nothing Then
        Call InOrder(TN.LeftChild, myCol)
        If myCol Is Nothing Then
            Set myCol = New Collection: myCol.add ("#: " & TN.Value & "  (" & TN.ValueCount & " Total)")
        Else
            myCol.add ("#: " & TN.Value & "  (" & TN.ValueCount & " Total)")
        End If
        Call InOrder(TN.RightChild, myCol)
    End If
    Set InOrder = myCol
End Function

Here is the "PreOrder" function of the "BinarySearchTree" class module. This function recurses the BST in the order of the root TreeNode, then the left TreeNode, then the right TreeNode. This could be used to get a prefix or to copy the BST but here I am displaying them. A Collection is returned but that variable could be an Array.

' public function to display the values from left to right (root, left, right) recursively
Public Function PreOrder(TN As TreeNode, Optional myCol As Collection) As Collection
    If Not TN Is Nothing Then
        If myCol Is Nothing Then
            Set myCol = New Collection: myCol.add ("#: " & TN.Value & "  (" & TN.ValueCount & " Total)")
        Else
            myCol.add ("#: " & TN.Value & "  (" & TN.ValueCount & " Total)")
        End If
        Call PreOrder(TN.LeftChild, myCol)
        Call PreOrder(TN.RightChild, myCol)
    End If
    Set PreOrder = myCol
End Function

Here is the "PostOrder" function of the "BinarySearchTree" class module. This function recurses the BST in the order of the left TreeNode, then the right TreeNode, then the right root TreeNode. This could be used to get a postfix or to delete the BST but here I am displaying them. A Collection is returned but that variable could be an Array.

' public function to display the values from right to left (left, right, root) recursively
Public Function PostOrder(TN As TreeNode, Optional myCol As Collection) As Collection
    If Not TN Is Nothing Then
        Call PostOrder(TN.LeftChild, myCol)
        Call PostOrder(TN.RightChild, myCol)
        If myCol Is Nothing Then
            Set myCol = New Collection: myCol.add ("#: " & TN.Value & "  (" & TN.ValueCount & " Total)")
        Else
            myCol.add ("#: " & TN.Value & "  (" & TN.ValueCount & " Total)")
        End If
    End If
    Set PostOrder = myCol
End Function

Points of Interest

Probably, the hardest obstacle I had was the fact that the recursive function kept de-referencing my pointers. A few "SET" key placements later and viola! It worked! I tried to keep the (O) notations small but had to add at least one extra step. I plan on adding a manual BST workbook in the future that would allow the user to insert, delete, and search for values instead of the automatic system that I have now. 

History

• 19^th February, 2019. V1.0.0: Initial release
• 23^rd February, 2019. V1.8.8: search, deleted, min and max functions added and all functions cleaned up