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]
- All nodes of left subtree are less than root node
- All nodes of right subtree are more than root node
- Both subtrees of each node are also
BST
s, 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.
Option Explicit
Private Const bstSize As Integer = 10: Private Const upperRnd As Integer = 10, lowerRnd As Integer = 1
Public WB As Workbook: Public WS As Worksheet: Public outPut As Collection
Public Sub Random_MAIN()
Application.ScreenUpdating = False
Dim loopCount, rndNumber As Integer: Dim BST As New BinarySearchTree: Dim root As TreeNode
Set WB = ThisWorkbook: Set WS = WB.Sheets("BST"): Set outPut = New Collection
For loopCount = 1 To bstSize
rndNumber = rndOmizer: Set root = BST.insert(root, rndNumber): outPut.add (rndNumber)
Next loopCount
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
Public ValueCount As Long
Public Value As Variant
Public LeftChild As TreeNode
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 insert(TN As TreeNode, valToInsert As Variant) As TreeNode
If TN Is Nothing Then
Set TN = New TreeNode
TN.Value = valToInsert
TN.ValueCount = 1
ElseIf TN.Value = valToInsert Then
TN.ValueCount = TN.ValueCount + 1
Else
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 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 delete(TN As TreeNode, valToDelete As Variant) As TreeNode
If valToDelete < TN.Value Then
Set TN.LeftChild = delete(TN.LeftChild, valToDelete)
ElseIf valToDelete > TN.Value Then
Set TN.RightChild = delete(TN.RightChild, valToDelete)
Else
Dim copyNode As TreeNode
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
Set copyNode = minValueNode(TN.RightChild): TN.Value = copyNode.Value: _
Set TN.RightChild = delete(TN.RightChild, copyNode.Value)
End If
End If
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 minValueNode(TN As TreeNode) As TreeNode
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 search(TN As TreeNode, valToSearch As Variant) As Boolean
Dim searchNode As TreeNode: Set searchNode = TN
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 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 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 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 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 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
- 19th February, 2019. V1.0.0: Initial release
- 23rd February, 2019. V1.8.8:
search
, deleted
, min
and max
functions added and all functions cleaned up