Binary Search Tree

Just like linked list, binary search tree is a node-based data structure.

The difference is that each node in a binary search tree has a maximum of two children, while a linked list node only has a "next" pointer.

Binary search tree also has three key properties:

1. The left subtree of a node must only contain nodes with keys that are lesser than the node's key.
2. The right subtree of a node must only contain nodes with keys that are greater than the node's key.
3. Both left and right subtrees are binary search trees themselves, and they have the above two properties.

Because of these properties of a BST, its operations can skip about half of the tree, instead of having to go through all items until you find your item.

That makes the time complexity of operations to be directly proportional to the logarithm of the height of the tree. It allows for binary search, which has a fast search, insertion and deletion of items. On average, the search, insertion and deletion operations take O(log n).

Other terms for a binary search tree:

• Ordered binary tree
• Sorted binary tree

Binary Search Tree vs. Linked List vs. Hash table#

Binary Search Tree Example Use Cases#

Binary search trees can be used to implement dynamic sets, lookup tables and priority queues, and used in sorting algorithms such as tree sort.

Binary Search Tree Methods#

1. add(data)
2. remove(data)
3. getMin() - returns the minimum data stored in a node in the tree
4. getMax() - returns the maximum data stored in a node in the tree
5. find(data) - returns the node that holds the data
6. isPresent(data) - returns a boolean that asserts if the data is present in the tree

Binary Search Tree TypeScript Implementation#

interface IBST {
    add(data: number): void;
    remove(data: number): void;
    getMin(): number | null;
    getMax(): number | null;
    find(data: number): BSTNode | undefined;
    isPresent(data: number): boolean;
}
export class BSTNode {
    data: number;
    left: BSTNode | null;
    right: BSTNode | null;
    constructor(data: number, left: BSTNode | null = null, right: BSTNode | null = null) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}
class BST implements IBST {
    private root: BSTNode | null = null;
    /**
     * @param node the starting point
     * @param data the data to add
     */
    private addNode(node: BSTNode, data: number): null | undefined {
        if (data < node.data) {
            if (node.left === null) {
                node.left = new BSTNode(data);
                return;
            } else {
                return this.addNode(node.left, data);
            }
        } else if (data > node.data) {
            if (node.right === null) {
                node.right = new BSTNode(data);
                return;
            } else {
                return this.addNode(node.right, data);
            }
        } else {
            return null;
        }
    }
    /**
     * @param node the starting point
     * @param data the data to find and remove its node
     */
    private removeNode(node: BSTNode | null, data: number): BSTNode | null {
        if (node === null) {
            return null;
        }
        if (data === node.data) { // found the node with the data
            if (node.left === null && node.right === null) { // node has no children
                return null;
            }
            if (node.left === null) {
                return node.right;
            }
            if (node.right === null) {
                return node.left;
            }
            
            // node has two children
            // move one step to the right, then go to the left-most after that
            let tempNode: BSTNode = node.right;
            while (tempNode.left !== null) {
                tempNode = tempNode.left;
            }
            node.data = tempNode.data; // replace node-to-remove's data with left-most node's data
            // set up the right part of the node correctly
            // remove left-most-node, because you already moved its data to its new correct place (node-to-remove's place)
            // replace node-to-remove's right tree with left-most-node's right tree
            node.right = this.removeNode(node.right, tempNode.data);
            return node;
        } else if (data < node.data) {
            // set up the left part of the node correctly
            node.left = this.removeNode(node.left, data);
            return node;
        } else {
            // set up the right part of the node correctly
            node.right = this.removeNode(node.right, data);
            return node;
        }
    }
    add(data: number): void {
        const node: BSTNode | null = this.root;
        if (node === null) {
            this.root = new BSTNode(data);
        } else {
            this.addNode(node, data);
        }
    }
    remove(data: number): void {
        if (this.isPresent(data)) {
            this.root = this.removeNode(this.root, data);
        }
    }
    getMin(): number | null {
        if (this.root === null) {
            return null;
        }
        let currentNode: BSTNode | null = this.root;
        while (currentNode.left !== null) {
            currentNode = currentNode.left;
        }
        return currentNode.data;
    }
    getMax(): number | null {
        if (this.root === null) {
            return null;
        }
        let currentNode: BSTNode | null = this.root;
        while (currentNode.right !== null) {
            currentNode = currentNode.right;
        }
        return currentNode.data;
    }
    find(data: number): BSTNode | undefined {
        if (this.root === null) {
            return undefined;
        }
        let currentNode: BSTNode | null = this.root;
        while (currentNode!.data !== data) {
            if (data < currentNode!.data) {
                currentNode = currentNode!.left;
            } else {
                currentNode = currentNode!.right;
            }
            if (currentNode === null) {
                return undefined;
            }
        }
        return currentNode;
    }
    isPresent(data: number): boolean {
        return !!this.find(data)
    }
}

This class only works on number data types to keep things simple. In the real world, BST classes can also work with strings and even objects. The class will then decide how to sort them when performing operations.

In our example, operations are simple - they use greater than or less than for comparison, since it's only dealing with numbers.

TODO tree traversal and tree height