This is a continuation of a series introducing data structures in javascript. A binary tree is a tree

based data structure in which each node has at most two child nodes. The child nodes are typically

referred to as the left and right nodes. Nodes with children are called parent nodes. The absolute

first node in the tree is referred to as the root node.

A binary search tree is a binary tree that is organized with the following properties:

– The left subtree of a node contains only nodes with keys that are less than the nodes key.

– The right subtree of a node contains only nodes with keys that are greater than the nodes key.

– Both the left and right subtrees must also be binary trees

With the data inserted into the tree in this manner, searching becomes more effecient than within an array

because traversal of the data structure can logically exclude elements for comparison. Traversing the structure

from the root node, a greater than or less than check will eliminate half of the data to be compared; assuming

that it is a perfectly balanced tree.

Each node in a binary search tree is similar to a doubly linked list in that they contain some data as well

as two pointers to other nodes. The key difference from a doubly linked list is that the nodes relate to

one another.

A javascript implementation of such a node would look like the following:

var node = { data: 17, left: null, right: null }

The first step in building a binary search tree implementation is to define a custom type with a single property

that represents the root node.

function BinarySearchTree() { this.root = null; }

To insert a value into the tree you must traverse the tree using the rules that are defined earlier in this document.

The one special case is when no root node exists; denoting that the node to be inserted is the root node.

BinarySearchTree.prototype = { insert: function(data){ var node = { data: data, left: null, right: null }; var currentNode; if (this.root === null){ this.root = node; } else { currentNode = this.root; while(true){ if (data < currentNode.data){ if (currentNode.left === null){ currentNode.left = node; break; } else { currentNode = currentNode.left; } } else if (data > currentNode.data){ if (currentNode.right === null){ currentNode.right = node; break; } else { currentNode = currentNode.right; } } else { break; } } } }, };

Removal of a node from a binary search tree is can be a complex operation because the

tree must remain balanced. This means that all values on the left must be less than

all of the values on the right. There are two special cases to consider when removing

a node as well; existence of the node must be checked as well as determination if the

node to be removed is the root node.

When removing a node, the number of children for that node must be taken into consideration

since the operations become slightly different depending on the number. Removing a node with

two children is the most complex.

BinarySearchTree.prototype = { remove: function(data){ var found = false; var parentNode = null; var currentNode = this.root; var childCount; var replacementNode; var replacementParent; while(!found && currentNode){ if (data < currentNode.data){ parentNode = currentNode; currentNode = currentNode.left; } else if (value > current.value){ parentNode = currentNode; currentNode = currentNode.right; } else { found = true; } } if (found){ childCount = (current.left !== null ? 1 : 0) + (current.right !== null ? 1 : 0); if (currentNode === this.root){ switch(childCount){ case 0: this.root = null; break; case 1: this.root = (currentNode.right === null ? currentNode.left : currentNode.right); break; case 2: replacementNode = this.root.left; while (replacementNode.right !== null){ replacementParent = replacementNode; replacementNode = replacementNode.right; } if (replacementParent !== null){ replacementParent.right = replacementNode.left; replacementNode.right = this.root.right; replacementNode.left = this.root.left; } else { replacementNode.right = this.root.right; } this.root = replacementNode; } } else { switch (childCount){ case 0: if (currentNode.data < parentNode.data){ parent.left = null; } else { parentNode.right = null; } break; case 1: if (currentNode.data < parentNode.data){ parentNode.left = (currentNode.left === null ? currentNode.right : currentNode.left); } else { parentNode.right = (currentNode.left === null ? currentNode.right : currentNode.left); } break; case 2: replacementNode = currentNode.left; replacementParent = currentNode; while(replacementNode.right !== null){ replacementParent = replacementNode; replacementNode = replacementNode.right; } replacementParent.right = replacementNode.left; replacementNode.right = currentNode.right; replacementNode.left = currentNode.left; if (currentNode.data < parentNode.data){ parentNode.left = replacementNode; } else { parentNode.right = replacementNode; } } } } }, };

A generic method to traverse the array is useful to have for cases where you may want

to convert the values in the tree to an array or a string.

BinarySearchTree.prototype = { traverse: function(evaluate){ function iterate(node){ if (node){ if (node.left !== null){ iterate(node.left); } evaluate.call(this, node); if (node.right !== null){ iterate(node.right); } } } iterate(this.root); }, toArray: function(){ var result = []; this.traverse(function(node){ result.push(node.data); }); return result; }, toString: function(){ return this.toArray().toString(); }, };

Below are some simple usage examples for this implementation of a binary

search tree in javascript.

var bst = new BinarySearchTree(); bst.add(17); bst.add(11); bst.add(43); bst.add(9); bst.add(65); bst.remove(43); document.writeln(bst.toString()); // prints 9 11 17 65

## Leave a Reply