Binary Search Tree

bst.js

// Tree node
var Node = function(data) {
    this.left = null;
    this.right = null;
    this.data = data;
    this.key = data.age;
    this.parent = null;
    
    // Replaces the current node with the data and key of another
    this.replaceWith = function(replacement) {
        this.data = replacement.data;
        this.key = replacement.key;
    };
};

// Main BST class
var BST = function() {
    this.trunk = null;
    this.deleteLeft = true;

    // Search the tree for a value with an optional parent node limiter
    this.search = function(val, node) {
        if (node === undefined) node= this.trunk;
        if (node == null || node.key == val) return node;
        else if (node.left != null && val < node.key) return this.search(val, node.left);
        else if (node.right != null && val > node.key) return this.search(val, node.right);
        else return null;
    };

    // Add a node to the tree with an optional parent
    this.add = function(node, parent) {
        if (this.trunk == null) this.trunk = node;
        else {
            if (parent == null) parent = this.trunk;
            node.parent = parent;
            if (node.key <= parent.key) {
                if (parent.left != null) this.add(node, parent.left);
                else parent.left = node;
            } else {
                if (parent.right != null) this.add(node, parent.right);
                else parent.right = node;
            }
        }
    };

    // Remove a node from the tree with an optional parent
    this.remove = function(val, parent) {
        var node = this.search(val, parent === undefined ? this.trunk : parent);
        if (node != null) {
            if (node.left == null && node.right == null) {
                if (node == this.trunk) this.trunk = null;
                else if (node.parent.left == node) node.parent.left = null;
                else node.parent.right = null;
            } else if(node.left != null && node.right != null) {
                var replacement = this.findMinimum(node.right);
                node.replaceWith(replacement);
                this.remove(replacement.key, node.right);
            } else {
                node.replaceWith(node.left || node.right);
            }
        }
    };
    
    // Find the minimum child element
    this.findMinimum = function(parent) {
        var temp = parent;
        while(temp.left != null) temp = temp.left;
        return temp;
    };
      
    // Travarse the tree
    this.traverse = function(order, parent) {
        if(parent === null) return '';
        if(parent === undefined) parent = this.trunk;
        var l = this.traverse(order, parent.left);
        var p = parent.key+',';
        var r = this.traverse(order, parent.right);
        return order == 1 ? p+l+r : (order == 2 ? l+p+r : l+r+p );
    } 
};

var tree = new BST();
tree.add(new Node({name: 'Bob', age: 14}));
tree.add(new Node({name: 'Jane', age: 12}));
tree.add(new Node({name: 'Jill', age: 9}));
tree.add(new Node({name: 'Amy', age: 13}));
tree.add(new Node({name: 'Brad', age: 27}));
tree.add(new Node({name: 'John', age: 21}));

tree.remove(12);

var str = tree.traverse(1, str);