bst.js

import {Node} from './node';

export class BinarySearchTree {

    constructor(root) {
        this.root = root;
        this.cmpFn = (l, r) => { return l - r; }; //cmp keys
    }

    get rootNode() {
        return this.root;
    }


    contains(key) {
        let found = false;
        let current = this.root;

        while (!found && current) {
            if (key === current.key) found = true;
            if (current && key < current.key) current = current.left;
            if (current && key > current.key) current = current.right;
        }
        return found;
    }


    add(key) {
        const newNode = new Node(null, null, key);
        if (!this.root) {
            this.root = newNode;
            return;
        }
        this.addNode(this.root, newNode);
    }

    addNode(root, newNode) {
        if (this.cmpFn(root.key, newNode.key) > 0) {
            if (root.left === null)
                root.left = newNode;
            else
                this.addNode(root.left, newNode)
        } else {
            if (root.right === null)
                root.right = newNode;
            else
                this.addNode(root.right, newNode)
        }
    }

    search(key) {
        //validation maybe
        return this.searchNode(this.root, key);
    }

    searchNode (node, key) {
            if (!node) {
                return null; // key not found
            }
            // console.log('Visiting ' + node.key)
            // console.log('cmp: ' + this.cmpFn(key, node.key));
            if (this.cmpFn(key, node.key) < 0) {
                return this.searchNode(node.left, key);
            } else if (this.cmpFn(key, node.key) > 0) {
                return this.searchNode(node.right, key);
            } else { // key is equal to node key
                return node;
            }
    }

    remove(key) {

        let found = false,
            parent = null,
            current = this.root,
            childCount,
            replacement,
            replacementParent;

        //make sure there's a node to search
        while (!found && current) {
            //if the key is less than the current node's, go left
            if (key < current.key) {
                parent = current;
                current = current.left;
                //if the key is greater than the current node's, go right
            } else if (key > current.key) {
                parent = current;
                current = current.right;
                //keys are equal, found it!
            } else {
                found = true;
            }
        }

        //only proceed if the node was found
        if (found) {
            //figure out how many children
            childCount = (current.left !== null ? 1 : 0) + (current.right !== null ? 1 : 0);

            //special case: the key is at the root
            if (current === this.root) {
                switch (childCount) {

                    //no children, just erase the root
                    case 0:
                        this.root = null;
                        break;
                    //one child, use one as the root
                    case 1:
                        this.root = (current.right === null ? current.left : current.right);
                        break;
                    //two children, little work to do
                    case 2:
                        //new root will be the old root's left child...maybe
                        replacement = this.root.left;
                        //find the right-most leaf node to be the real new root
                        while (replacement.right !== null) {
                            replacementParent = replacement;
                            replacement = replacement.right;
                        }
                        //it's not the first node on the left
                        if (replacementParent !== null) {
                            //remove the new root from it's previous position
                            replacementParent.right = replacement.left;
                            //give the new root all of the old root's children
                            replacement.right = this.root.right;
                            replacement.left = this.root.left;
                        } else {
                            //just assign the children
                            replacement.right = this.root.right;
                        }

                        //officially assign new root
                        this.root = replacement;

                    //no default
                }

                //non-root values
            } else {

                switch (childCount) {

                    //no children, just remove it from the parent
                    case 0:
                        //if the current key is less than its parent's, null out the left pointer
                        if (current.key < parent.key) {
                            parent.left = null;

                            //if the current key is greater than its parent's, null out the right pointer
                        } else {
                            parent.right = null;
                        }
                        break;

                    //one child, just reassign to parent
                    case 1:
                        //if the current key is less than its parent's, reset the left pointer
                        if (current.key < parent.key) {
                            parent.left = (current.left === null ? current.right : current.left);

                            //if the current key is greater than its parent's, reset the right pointer
                        } else {
                            parent.right = (current.left === null ? current.right : current.left);
                        }
                        break;

                    //two children, a bit more complicated
                    case 2:

                        //reset pointers for new traversal
                        replacement = current.left;
                        replacementParent = current;

                        //find the right-most node
                        while (replacement.right !== null) {
                            replacementParent = replacement;
                            replacement = replacement.right;
                        }

                        replacementParent.right = replacement.left;

                        //assign children to the replacement
                        replacement.right = current.right;
                        replacement.left = current.left;

                        //place the replacement in the right spot
                        if (current.key < parent.key) {
                            parent.left = replacement;
                        } else {
                            parent.right = replacement;
                        }

                    //no default

                }
            }
        }
    }
     

    depth(root) {
        if (root === null) {
            return 0;
        }
        let leftDepth = this.depth(root.left);
        let rightDepth = this.depth(root.right);

        return (leftDepth > rightDepth) ? 1 + leftDepth : 1 + rightDepth;
    }

    inOrderTraversal(cb) {
        this.inOrderTraverseNode(this.root, cb);
    }

    inOrderTraverseNode(node, cb) {
        if (node) {
            this.inOrderTraverseNode(node.left, cb);
            cb(node.key);
            this.inOrderTraverseNode(node.right, cb);
        }
    }

    preOrderTraversal(cb) {
        this.preOrderTraverseNode(this.root, cb);
    }

    preOrderTraverseNode(node, cb) {
        if (node) {
            cb(node.key);
            this.preOrderTraverseNode(node.left, cb);
            this.preOrderTraverseNode(node.right, cb);
        }
    }


    postOrderTraversal(cb) {
        this.postOrderTraverseNode(this.root, cb);
    }

    postOrderTraverseNode(node, cb) {
        if (node) {
            this.postOrderTraverseNode(node.left, cb);
            this.postOrderTraverseNode(node.right, cb);
            cb(node.key);
        }
    }

}