Binary Search Tree in JavaScript (Data Structures)

A binary Search Tree is a node-based binary tree data structure. It has the following properties:

1. Every parent node has at most two children.

2. Every node to the left is always less than the parent node.

3. Every node to the right is always greater than the parent node.

Tree Terminology:

1. Root: Topmost node in the tree.

2. Child: A node directly connected to another node when moving away from the root.

3. Parent: The converse notion of a child.

4. Siblings: A group of nodes with the same parent.

5. Leaf: A node with no children.

6. Edge: A connection between one node and another.

Todos:

1. Insert

2. Search

Creating a node: It contains a value and two pointers - left and right.

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

Binary Search Tree:

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

Insertion:

1. Create a node from the value passed in the function.

2. Starting at the root:

• Check if there is a root, if not, the new node becomes the root.

• If there is a root, check if the value of the new node is greater than or less than the value of the root.

3. If the value is greater: check to see if there is a node to the right.

• If there is, move to that node and repeat the steps.

• Add that node as the right property.

4. If the value is less: check to see if there is a node to the left.

• If there is, move to that node and repeat these steps.

• If there is not, add that node as the left property.

    // insert - Iterative
        insert(val) {
            let newNode = new Node(val);
            if(this.root === null) {
                this.root = newNode;
                return this;
            }
  
            let current = this.root;
            while(true) {
                if(val === current.val) return undefined;
                if(val < current.val) {
                    if(current.left === null) {
                        current.left = newNode;
                        return this;
                    }
                    current = current.left;
                } else {
                    if(current.right === null) {
                        current.right = newNode;
                        return this;
                    }
                    current = current.right;
                }
            }
        }
  

Search:

1. Starting at the root:

• Check if there is a root, if not then we’re done.

• If there is a root, check if the value of the new node is equal to the value we’re looking for. If found, we’re done.

• If not, check to see if the value is greater than or less than the value of the root.

2. If it’s greater: check to see if there is a node to the right.

• If there is a node, move to that node and repeat the same steps.

• If there’s not, we’re done searching.

3. If it’s less: check to see if there is a node to the left.

• If there is, move to that node and repeat the same steps.

• If there is not, we’re done searching.

    // find
    find(val) {
            if(this.root === null) return false;
            let current = this.root, 
                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;
        }
  

---

Time Complexity of Binary Search Tree:

• Access: O(log(n))

• Search: O(log(n))

• Insertion: O(log(n))

• Removal: O(log(n))