I have been creating some data structures to keep my skills sharp. I created a BST and have been stress testing its speed against an array. I noticed that the insertion speed for the BST is far slower than the array.push. I have been using Math.random and adding millions of numbers to both data structures. Oddly the BST is much faster at finding a value then the array.includes/indexOf. Is there a better way to code my insert function or is inserting just a slow part with BST
Here is my code
insert(data) {
if(this.root === null) {
this.root = new Node(data)
return this
}
let current = this.root
while(current) {
if(current.data === data) {
console.log(data + ' Already exists in tree')
return
}
if(data < current.data) {
if(current.left === null) {
current.left = new Node(data)
this.size++
return this
}
current = current.left
}
if(data > current.data) {
if(current.right === null) {
current.right = new Node(data)
this.size++
return this
}
current = current.right
}
}
}
Your code is perfectly fine.
TL;DR: Your comparison/performance benchmark is inaccurate
My answer assumes you are familiar with the Big O notation for time measurement of algorithms, if you aren't do say so in a comment and I will edit my answer.
The thing is, array.push is a simple operation since it always appends the element at the end of the array, which takes O(1) (constant) time, while inserting an element into a BST means you are looking for the right place to insert it, because it has to be in order, you don't just chuck it at the end of the tree like you do with array,push. This operation takes more time (O(logn) where n is the number of nodes in the tree, to be precise), so if you compare these two, of course array.push will be faster.
If you tried inserting an element in order into the array, it would have been much much slower than inserting it into a BST, because you would have to search each and every element in the array until you come to the right spot, then move everything to fit your new element in the array, which takes O(n) time, where n is the number of elements in the array.
So in conclusion, BST excel at finding and inserting elements in order, and when the order doesn't matter and you can just put the element wherever, array will usually do it faster, so that's why searching in your BST is faster than includes or indexOf for an array