Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I recently decided to make a LinkedList and binary search tree using JavaScript. I wanted to reach out to a wider audience and see how I did, and where could I improve.

Linked List:

var Node = function(value) {
    this.value = value;
    this.next=null;
    return this;
};

var LinkedList = function(node){
    this.head = node;
    return this;
};

LinkedList.prototype.insertEnd = function(newNode, currentNode) {
    var currentNode = currentNode || this.head;

    if(currentNode.next !== null) {
        return this.insertEnd(newNode, currentNode.next);
    } else {
        currentNode.next = newNode;
    }
};

LinkedList.prototype.insertBeginning = function(newNode) {
    newNode.next = this.head;
    this.head = newNode;
};

LinkedList.prototype.search = function(searchValue, currentNode) {
    var currentNode = currentNode || this.head;
    if(currentNode.value == searchValue) {
        console.log("true");
        return true;
    } else if(currentNode.next !== null) {
        return this.search(searchValue, currentNode.next);
    }
    console.log("not found");
    return false;
};
LinkedList.prototype.remove = function(deleteValue, currentNode, parentNode) {
    currentNode = currentNode || this.head;
    if(currentNode.value === deleteValue) {
        if(currentNode.next !== null) {
            parentNode.next = currentNode.next;
        } else {
            parentNode.next = null; 
        }               
    } else if(currentNode.next !== null) {
        return this.remove(deleteValue, currentNode.next, currentNode);
    }
};

LinkedList.prototype.size = function(currentNode, size) {
    var currentNode = currentNode || this.head;
    var size = size || 1;
    if(currentNode.next !== null) {
        return this.size(currentNode.next, size+1);
    } else {
        console.log(size);
        return size;
    }
};

(function(){
    // LinkedList Example
    var linkedList = new LinkedList(new Node("oldHead"));
    linkedList.insertEnd(new Node(2));
    linkedList.insertEnd(new Node("cat"));
    linkedList.insertEnd(new Node("dog"));
    linkedList.insertEnd(new Node(100));

    linkedList.search("cat");
    linkedList.size();
    linkedList.remove("cat");
    linkedList.size();
    linkedList.search("cat");
    console.log("current head: "+linkedList.head.value);
    linkedList.insertBeginning(new Node("testBeginningInsert"));
    console.log("current head: "+linkedList.head.value);
    linkedList.size();
})();

Binary Search Tree:

var Node = function(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    return this;
};

Node.prototype.insert = function(newNode) { 
    if(newNode.value < this.value) {
        if(this.left === null) {
            this.left = newNode;
        } else {
            this.left.insert(newNode);
        }
    } else if(newNode.value > this.value) {
        if(this.right === null) {
            this.right = newNode;
        } else {
            this.right.insert(newNode);
        }
    } else {
        return true;
    }
};

Node.prototype.depthFirstSearch = function(searchValue) {
    console.log(searchValue+": "+this.value);
    if(this.value === searchValue) {
        console.log("search item found");
        return true;
    } else if(searchValue < this.value && this.left !== null) {
        return this.left.depthFirstSearch(searchValue);
    } else if(searchValue > this.value && this.right !== null) {
        return this.right.depthFirstSearch(searchValue);
    } else {
        console.log("could not find "+searchValue);
        return false;
    }
};


Node.prototype.inorderTraversal = function() {  
    if(this.left !== null) {
        this.left.inorderTraversal();
    }
    console.log(this.value);
    if(this.right !== null) {
        this.right.inorderTraversal();
    }
};

Node.prototype.preOrderTraversal = function() { 
    console.log(this.value);
    if(this.left !== null) {
        this.left.preOrderTraversal();
    }   
    if(this.right !== null) {
        this.right.preOrderTraversal();
    }
};

Node.prototype.postOrderTraversal = function() {        
    if(this.left !== null) {
        this.left.postOrderTraversal();
    }   
    if(this.right !== null) {
        this.right.postOrderTraversal();
    }
    console.log(this.value);
};

var BinarySearchTree = function(insertNode) {
    if(insertNode instanceof Node) {
        this.root = insertNode;
    } else {
        this.root = new Node(insertNode);
    }
    return this;
};

BinarySearchTree.prototype.insert = function(insert) {  
    if(insert instanceof Node) {
        this.root.insert(insert);
    } else {
        this.root.insert(new Node(insert));
    }
};

BinarySearchTree.prototype.depthFirstSearch = function(searchValue) {
    this.root.depthFirstSearch(searchValue);
};

BinarySearchTree.prototype.breadthFirstTraversal = function() {
    console.log("Breadth First Traversal");

    // For our intensive purposes,
    // our array is acting as a queue for us.
    var queue = [],
        current = this.root;

    if(current !== null) {
        queue.push(current);
    }

    // start off enqueing root
    while(queue.length > 0) {
        var tempNode = queue.shift();
        console.log(tempNode.value); // Visit current node
        if(tempNode.left !== null) {
            queue.push(tempNode.left);
        }
        if(tempNode.right !== null) {
            queue.push(tempNode.right);
        }       
    }   
};

BinarySearchTree.prototype.inOrderTraversal = function(){
    this.root.inorderTraversal();
};
BinarySearchTree.prototype.preOrderTraversal = function(){
    this.root.preOrderTraversal();
};
BinarySearchTree.prototype.postOrderTraversal = function(){
    this.root.postOrderTraversal();
};


// Gotta not hurt dat global namespace
(function(){

    // Example BinBinarySearchTree
    var bst = new BinarySearchTree(50);
    bst.insert(25);bst.insert(75);bst.insert(12);bst.insert(37);bst.insert(87);bst.insert(63);

    console.log("Inorder Traversal");
    bst.inOrderTraversal();

    console.log("Preorder Traversal");
    bst.preOrderTraversal();

    console.log("Postorder Traversal");
    bst.postOrderTraversal();

    console.log("Search for valid (63)");
    bst.depthFirstSearch(63);

    console.log("Search for invalid (19)");
    bst.depthFirstSearch(19);   

    bst.breadthFirstTraversal();
})();
share|improve this question

1 Answer 1

up vote 3 down vote accepted

Most of your code looks like textbook code.

Your size function shouldn't have to take a second argument.

LinkedList.prototype.size = function(currentNode /* optional */) {
    // var currentNode, shadowing the currentNode param, is weird
    var node = currentNode || this.head;
    // I prefer to put the base case first
    if (node.next == null) {
        return 1;
    } else {
        return 1 + this.size(node.next);
    }
};

Your traversal functions should not hard-code console.log() as the action. For flexibility, they should take a visitor function as a callback.

// Fixed capitalization of "inOrderTraversal"
Node.prototype.inOrderTraversal = function(visitor) {  
    if (this.left !== null) {
        this.left.inOrderTraversal(visitor);
    }
    visitor(this.value);
    if(this.right !== null) {
        this.right.inOrderTraversal(visitor);
    }
};

// Elsewhere...
tree.inOrderTraversal(console.log);
share|improve this answer
    
"Most of your code looks like textbook code." Welp, I wrote this from scratch; it was intended as an educational refresher, so if it looks close to textbook... great! I have one inconsistency with my implementation of LinkedList and BST. The LinkedList implementation makes recursive calls to itself. For the BST, the traversals are delegated to the Node object, which it will then make recursive calls to other Node elements. Which was done closer to the "right" way? –  TheIronDeveloper Sep 19 '13 at 3:43
    
I think you've done the right thing in each case. –  200_success Sep 19 '13 at 4:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.