Binary Search Tree(JavaScript and Python)

What is a binary search tree?

A binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers.

It is called a binary tree because each tree node has a 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 value of the key of the left sub-tree is less than the value of its parent (root) node's key. The value of the key of the right sub-tree is greater than or equal to the value of its parent (root) node's key.
The logic being lower value as compared to the parent node should always be on the left.

Here is an amazing site to visualize the different operations on Binary Tree and other data structures visualgo

Operation on Binary Search Tree

• Insertion
• Search

Insertion

When a value is to be inserted, we must first find its proper location.

1. First we have to check if there exists a root node if not we insert the value at the root.
2. If we have a root value then we check if the value is less or greater than the parent node.
3. If the value is less than the parent move to the left and check if the location is empty if not do a greater than or less then check with that value and move either to the right or left. if you find an empty location with the criteria above insert the value. 4 return the tree when done.

Code implementation in JavaScript:

class Node{
    constructor(val){
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BST{
    constructor(){
        this.root = null;
    }

    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
                    }
                }
            }

        }

    }

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            

There is an issue that arises when implementing a BST. That is how do you handle equality. This is an edge case and the person implementing the BST might have to make a decision that best suits them, from either ignoring it outright or returning undefined or null or None. My choice was to insert on the right always if equality is ever encountered.
Next on the series, I will implement the search functionality.