Data structures and algorithms

Binary Search Tree

Learn Simpli May 23, 2021 no Comments

Binary Search Tree

Definition:

Is an ordered tree
Is a binary tree where nodes with lesser values are placed to the left of the root node and nodes with equal or greater values are placed to the right

Rules

Rule 1: All child node in the tree to the right of the root node must be greater or equal to the current or left node
“Rule 2: Node can only have at most 2 children

Advantages

Searching the is very easy and fast

Tree Traversal

Pre-order: The node is visited before its children
In order: The left child is visited before the node and then the roght child
Postorder: The left and Right child are visited before the node

Write a code

Now let’s write a code in javascript for the binary search tree

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

class BinarySearchTree {
    constructor() {
        this.root = null;
    }
    insert(data) {
        const newNode = new Node(data);
        if (this.root === null) {
            this.root = newNode;
        } else {
            let currentNode = this.root;
            while (true) {
                if (data < currentNode.data) {
                    //Left
                    if (!currentNode.left) {
                        currentNode.left = newNode;
                        return this;
                    }
                    currentNode = currentNode.left;
                } else {
                    //Right
                    if (!currentNode.right) {
                        currentNode.right = newNode;
                        return this;
                    }
                    currentNode = currentNode.right;
                }
            }
        }
    }
    lookup(data) {
        if (!this.root) {
            return false;
        }
        let currentNode = this.root;
        while (currentNode) {
            if (data < currentNode.data) {
                currentNode = currentNode.left;
            } else if (data > currentNode.data) {
                currentNode = currentNode.right;
            } else if (currentNode.data === data) {
                return currentNode;
            }
        }
        return null
    }
    remove(data) {
        if (!this.root) {
            return false;
        }
        let currentNode = this.root;
        let parentNode = null;
        while (currentNode) {
            if (data < currentNode.data) {
                parentNode = currentNode;
                currentNode = currentNode.left;
            } else if (data > currentNode.data) {
                parentNode = currentNode;
                currentNode = currentNode.right;
            } else if (currentNode.data === data) {
                if (currentNode.right === null) {
                    if (parentNode === null) {
                        this.root = currentNode.left;
                    } else {
                        if (currentNode.data < parentNode.data) {
                            parentNode.left = currentNode.left;
                        } else if (currentNode.data > parentNode.data) {
                            parentNode.right = currentNode.left;
                        }
                    }
                } else if (currentNode.right.left === null) {
                    currentNode.right.left = currentNode.left;
                    if (parentNode === null) {
                        this.root = currentNode.right;
                    } else {
                        if (currentNode.data < parentNode.data) {
                            parentNode.left = currentNode.right;
                        } else if (currentNode.data > parentNode.data) {
                            parentNode.right = currentNode.right;
                        }
                    }
                } else {
                    let leftmost = currentNode.right.left;
                    let leftmostParent = currentNode.right;
                    while (leftmost.left !== null) {
                        leftmostParent = leftmost;
                        leftmost = leftmost.left;
                    }
                    leftmostParent.left = leftmost.right;
                    leftmost.left = currentNode.left;
                    leftmost.right = currentNode.right;

                    if (parentNode === null) {
                        this.root = leftmost;
                    } else {
                        if (currentNode.data < parentNode.data) {
                            parentNode.left = leftmost;
                        } else if (currentNode.data > parentNode.data) {
                            parentNode.right = leftmost;
                        }
                    }
                }
                return true;
            }
        }
    }
}

function treeTraversal(node) {
    const tree = { data: node.data };
    tree.left = node.left === null ? null : treeTraversal(node.left);
    tree.right = node.right === null ? null : treeTraversal(node.right);
    return tree;
}

const treeInstance = new BinarySearchTree();
treeInstance.insert(20)
treeInstance.insert(50)
treeInstance.insert(30)
console.log(JSON.stringify(treeTraversal(treeInstance.root)))
treeInstance.remove(30)
console.log(JSON.stringify(treeTraversal(treeInstance.root)))
// Output
// {"data":20,"left":null,"right":{"data":50,"left":{"data":30,"left":null,"right":null},"right":null}}
// {"data":20,"left":null,"right":{"data":50,"left":null,"right":null}}