ES6 functions for manipulating a Binary Search Tree

bst.js

/*
 * Based on the work of Nicholas C. Zakas
 * https://github.com/nzakas/computer-science-in-javascript/
 */

class Node {
    constructor(value = null, left = null, right = null) {
        this.value = value;
        this.right = right;
        this.left = left;
    }
  
    toString() {
        return JSON.stringify(this);
    }
}

class BST {
    constructor(node = null) {
        this.root = node;
    }
    
    /*
     * A recursive in-order traversal. Takes a callback function, process, which is applied to each node.
     */
     
    recursiveInOrder(process) {
        let inOrder = (node) => {
            if (node.left !== null) {
                inOrder(node.left);
            }

            process.call(this, node);

            if (node.right !== null) {
                inOrder(node.right);
            }
        };

        inOrder(this.root);
    }
    
    /*
     * A recursive pre-order traversal.
     */
    
    recursivePreOrder(process) {
        let preOrder = (node) => {
            process.call(this, node);
            
            if(node.left !== null) {
                preOrder(node.left);
            }
            
            if(node.right !== null) {
                preOrder(node.right);
            }
        }
        
        preOrder(this.root);
    }
    
    /*
     * A recursive post-order traversal.
     */
    
    recursivePostOrder(process) {
        let postOrder = (node) => {
            if(node.left !== null) {
                postOrder(node.left);
            }
            
            if(node.right !== null) {
                postOrder(node.right);
            }
            
            process.call(this, node);
        }
        
        postOrder(this.root);
    }
    
    /*
     * Searches for a value in the tree and returns a node.
     */
     
    find(value) {
        let result;
        let traverse = (node) => {
            if (node === null) {
                return;
            } else if (node.value === value) {
                result = node;
            } else if (value < node.value) {
                traverse(node.left);
            } else if (value > node.value) {
                traverse(node.right);
            }
        };
        traverse(this.root);
        return result;
    }
    
    /*
     * Takes an array of values to insert into the tree.
     */
     
    insert(values) {
        values.forEach((value) => {
            let current;

            if (this.root === null) {
                this.root = new Node(value);
            } else {
                current = this.root;
                while (true) {
                    if (value > current.value) {
                        if (current.right === null) {
                            current.right = new Node(value);
                            break;
                        } else {
                            current = current.right;
                        }
                    } else if (value < current.value) {
                        if (current.left === null) {
                            current.left = new Node(value);
                            break;
                        } else {
                            current = current.left;
                        }
                    }
                }
            }
        }, this);
    }
    
    /*
     * Returns a boolean indicating whether a given value is contained in the tree.
     */
     
    contains(value) {
        return !!this.find(value);
    }
    
    /*
     * Returns an integer indicating the number of nodes in the tree.
     */
     
    size() {
        let length = 0;
        this.recursiveInOrder(() => {
            length++;
        });
        return length;
    }
    
    /*
     * Returns an array containing the tree's nodes, in ascending order.
     */
     
    toArray() {
        let arr = [];
        this.recursiveInOrder((node) => {
            arr.push(node);
        });
        return arr;
    }
    
    /*
     * Returns the tree in order as a serialized JSON string.
     */
     
    toString() {
        let str = '';
        this.recursiveInOrder((node) => {
            str += JSON.stringify(node) + '\n';
        });
        return str;
    }
    
    /*
     * Returns the node with the nth-largest value in the tree.
     */
    
    nthLargest(n) {
        let arr = this.toArray();
        return arr[arr.length - (n + 1)];
    }
    
    /*
     * Returns the node with the nth-smallest value in the tree.
     */
    
    nthSmallest(n) {
        let arr = this.toArray();
        return arr[n];
    }
}