LinkedList and binary search tree in JavaScript

Question

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();
})();

Answer 1

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);

• TheIronDeveloper: "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?
• 200_success: I think you've done the right thing in each case.

Answer 2

For LinkedList remove function, if the deleteValue is same as head's, the function should be failed, here is a modified version:

LinkedList.prototype.remove = function(deleteValue, currentNode, parentNode) {
 currentNode = currentNode || this.head;
 if (currentNode.value === deleteValue) {
 if (currentNode.value === this.head.value) {
 this.head = currentNode.next;
 } else if (currentNode.value === this.tail.value) {
 parentNode.next = null;
 this.tail = parentNode;
 } else {
 parentNode.next = currentNode.next;
 }
 } else if (currentNode.next !== null) {
 return this.remove(deleteValue, currentNode.next, currentNode);
 }
};

Besides, I prefer to keep a tail to make insertEnd faster, like:

var LinkedList = function(newNode) {
 this.head = newNode || null;
 this.tail = newNode || null; // storing a reference to the end of the list
 return this;
};

Then insertEnd should not need a recursive, like:

LinkedList.prototype.insertEnd = function (newNode) {
 if (!(newNode instanceof Node)) {
 newNode = new Node(newNode);
 }
 if(!this.head) {
 this.head = newNode;
 this.tail = this.head;
 } else {
 // Switch to use tail for good performance
 this.tail.next = newNode;
 this.tail = this.tail.next;
 }
};