Binary Search Tree Series Part 2

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:

1. First create variables current, it to the root node and found set it to false.
2. Start looping while the current node exists and the found variable is still false.
3. If the value is less than the value stored in the current node then set current to the left property of the current variable
4. If the value is greater than the current's value property then set the current to the current variable right property.
5. Otherwise set found variable to true.
6. 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.