A Very Basic Recursive Binary Search Tree For Excel VBA
1.33/5 (2 votes)
An unbalanced basic recursive Binary Search Tree for Excel VBA with functions (insert, search, delete, in order, pre-order, post-order, minimum, and maximum)
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
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
- 19th February, 2019. V1.0.0: Initial release
- 23rd February, 2019. V1.8.8:
search,deleted,minandmaxfunctions added and all functions cleaned up