Binary Search Tree Series Part 2
Edwin
Posted on March 9, 2021
Find or Search Implementation.
When looking for a node with a particular value on the tree, the arrangement of the nodes where the lesser value than the parent node. This means there is a particular optimization done when storing data in a binary tree. After every iteration when looking for the node the number of possible nodes is halved. This lets us get to the solution much more quickly.
Example.
Given we have 1000,000 elements in our data stored in an array and the array is sorted. Assume the node we are searching for is near the end of the let's say 1000,000nth node, Instead of making 1 million comparisons looking the for the node since we know our array is sorted we would compare our value with the middle value in the array, if the value is greater than the middle value then we would know the value most probably exists in the top half of the array(from element 500,000- 1000,000) I say probably because the value might not exist at all in our data and we have to account for the possibility. By gaining this key insight we can ignore the bottom half of our array and make the next comparisons between our target value and the middle value in the top half of the array which would be the 750,000th element. We do this iteratively until we find or value or reach the end in which we return -1 or not found. This search methodology is faster because it always is eliminating half the search data where there is 100% certainty the value does not exist.from 1000,000, to 500,000 ... 250,000... 125,000,
The time complexity becomes O(log n) instead of O(n^2). See the below
as a reference.
This is exactly how the search works in a tree.
Pseudo Code/ Steps to follow:
- First create variables current, it to the root node and found set it to false.
- Start looping while the current node exists and the found variable is still false.
- If the value is less than the value stored in the current node then set current to the left property of the current variable
- If the value is greater than the current's value property then set the current to the current variable right property.
- Otherwise set found variable to true.
- outside the while check if the found is still false then return undefined if it is, otherwise returns the current variable Code implementation in JavaScript:
class Node{
constructor(val){
this.val = val;
this.left = null;
this.right = null;
}
}
class BST{
constructor(){
this.root = null;
}
// implementation and explanation in the first part of the //series.
insert(val){
let newNode = new Node(val);
if(!this.root){
this.root = newNode;
}else{
let current = this.root;
while(true){
if(val < current.val){
if(current.left === null){
current.left = newNode;
return this
}else{
current = current.left;
}
}else{
if(current.right === null){
current.right = newNode;
return this
}else{
current = current.right
}
}
}
}
}
find(val){
let current = this.root;
let found = false;
while(current && !found){
if(val < current.val){
current = current.left;
}
}else if(val > current.val){
current = current.right;
}else{
found = true
}
}
if(!found) return undefined
return current
}
}
In Python:-
class Node:
def __init__(self,val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root= None
def insert(self, val):
newNode = Node(val)
if self.root == None:
self.root= newNode
else:
current = self.root
while True:
if val< current.val:
if current.left == None:
current.left = newNode
return self
else:
current= current.left
else:
if(current.right == None):
current.right = newNode
return self
else:
current = current.right
def find(self, val):
current= self.root
found = False
while current and not found:
if val < current.val:
current = current.left
elif val > current.val:
current= current.right
else:
found = True
if(not found): return "not found"
return current
bst = BST()
bst.insert(100)
bst.insert(200)
bst.insert(150)
bst.insert(175)
bst.insert(160)
bst.insert(180)
bst.insert(75)
bst.insert(50)
bst.insert(65)
bst.insert(40)
bst.insert(55)
bst.insert(20)
print(bst.find(21))
Next in this series, we will take a look at the search Methodologies. Starting with Breadth-First Search.
Posted on March 9, 2021
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.