Published
Edited
Jun 21, 2018
Insert cell
md`# Javascript Tree data structure implementation`
Insert cell
function TreeNode(value) {
this.value = value;
this.left = null;
this.right = null;
}
Insert cell
function Tree() {
this.root = null;
this.count = 0;
}
Insert cell
traverse = Tree.prototype.traverse = function traverse(){
var stack = [];
var node = this.root;
if ( !node ) return null;
while ( node ) {
if ( node.left ) {
stack.push( node );
node = node.left;
} else if ( node.right ){
console.log( node );
node = node.right;
} else {
console.log( node );
node = stack.pop();
if ( node ) {
console.log( node );
node = node.right;
}
}
}
}
Insert cell
add = Tree.prototype.add = function add(node){
var current;
if( !this.root ) {
this.root = node;
this.count += 1;
return;
}
current = this.root;
while ( current ) {
if ( current.value > node.value ) {
if ( !current.left ) {
current.left = node;
current = null;
this.count += 1;
} else {
current = current.left;
}
} else {
if ( !current.right ) {
current.right = node;
current = null;
this.count += 1;
} else {
current = current.right;
}
}
}
}
Insert cell
find = Tree.prototype.find = function( value, current ){
current = current || this.root;
var parent = null;
while ( current ) {
if ( current.value === value ) {
return { current, parent };
} else if( current.value > value ){
parent = current;
current = current.left;
} else {
parent = current;
current = current.right;
}
}
return null;
}
Insert cell
updateTreeParentNode = Tree.prototype.updateTreeParentNode = function( parent, node, value ){
if( !parent ) { this.root = value; } else {
if ( parent.value > node.value ) {
parent.left = value;
} else {
parent.right = value;
}
}
}
Insert cell
findTopMostLeft = Tree.prototype.findTopMostLeft = function( node ){
var parent = null;
while ( node.left ) {
parent = node;
node = node.left;
}
return { node, parent }
}
Insert cell
remove = Tree.prototype.remove = function remove( value ) {
var node = this.find( value ).current;
var parent = this.find( value ).parent;
var topMostLeft = null;
if ( !node ) return null;
if ( !node.left ) {
if ( !node.right ) {
this.updateTreeParentNode( parent, node, null );
} else {
this.updateTreeParentNode( parent, node, node.right );
}
} else if ( !node.right.left ) {
node.right.left = node.left;
this.updateTreeParentNode( parent, node, node.right );
} else {
topMostLeft = this.findTopMostLeft( node.right );
topMostLeft.parent.left = null;
topMostLeft.node.left = node.left;
topMostLeft.node.right = node.right;
this.updateTreeParentNode( parent, node, topMostLeft.node );
}
this.count -= 1;
}
Insert cell
test_add = {
var tree = new Tree();
tree.add(new TreeNode(6));
tree.add(new TreeNode(4));
tree.add(new TreeNode(8));
tree.add(new TreeNode(1));
tree.add(new TreeNode(5));
tree.add(new TreeNode(10));
return tree;
}
Insert cell
test_find = {
var tree = new Tree();
tree.add(new TreeNode(6));
tree.add(new TreeNode(4));
tree.add(new TreeNode(8));
tree.add(new TreeNode(1));
tree.add(new TreeNode(5));
tree.add(new TreeNode(10));
return tree.find(5);
}
Insert cell
test_remove = {
var tree = new Tree();
tree.add(new TreeNode(6));
tree.add(new TreeNode(4));
tree.add(new TreeNode(8));
tree.add(new TreeNode(1));
tree.add(new TreeNode(5));
tree.add(new TreeNode(10));
tree.add(new TreeNode(7));
tree.add(new TreeNode(15));
tree.add(new TreeNode(9));
tree.remove(8);
return tree;
}
Insert cell
test_traverse = {
var tree = new Tree();
tree.add(new TreeNode(6));
tree.add(new TreeNode(4));
tree.add(new TreeNode(8));
tree.add(new TreeNode(1))
tree.add(new TreeNode(5));
tree.add(new TreeNode(10));
tree.add(new TreeNode(7));
tree.add(new TreeNode(15));
tree.add(new TreeNode(9));
tree.traverse()
}
Insert cell
printWords = function printWords( spaceDelimitedWordsString ) {
if ( typeof spaceDelimitedWordsString !== 'string' ) return;
spaceDelimitedWordsString.split(" ").reduce(function(tree, word){
tree.add( new TreeNode(word));
return tree
}, new Tree).traverse()
}
Insert cell
printWords("како сте шо прајте!")
Insert cell

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
Learn more