Skip to content

Instantly share code, notes, and snippets.

@hkasera
Last active August 29, 2015 14:02
Show Gist options
  • Save hkasera/0a3c935bd5b4f3765431 to your computer and use it in GitHub Desktop.
Save hkasera/0a3c935bd5b4f3765431 to your computer and use it in GitHub Desktop.
Binary Tree in Javascript
var BinaryTree = function (val) {
'use strict';
this.val = val || null;
this.left = null;
this.right = null;
};
BinaryTree.prototype.create = function (num) {
'use strict';
var i;
for (i = 0; i <= num; i = i + 1) {
this.insert(Math.floor(Math.random() * 50));
}
};
BinaryTree.prototype.insert = function (val) {
'use strict';
if (!this.val) {
this.val = val;
return;
}
if (val > this.val) {
if (!this.right) {
this.right = new BinaryTree(val);
return;
}
this.right.insert(val);
return;
}
if (val < this.val) {
if (!this.left) {
this.left = new BinaryTree(val);
return;
}
this.left.insert(val);
return;
}
};
BinaryTree.prototype.depth = function () {
'use strict';
if (!this.val) {
return 0;
}
var d_right, d_left;
if (this.right) {
d_right = (1 + this.right.depth());
} else {
d_right = 0;
}
if (this.left) {
d_left = (1 + this.left.depth());
} else {
d_left = 0;
}
if (d_right > d_left) {
return d_right;
}
return d_left;
};
BinaryTree.prototype.preorder = function () {
'use strict';
if (this.val === null) {
return;
}
console.log(this.val);
if (this.left) {
this.left.preorder();
}
if (this.right) {
this.right.preorder();
}
};
BinaryTree.prototype.inorder = function () {
'use strict';
if (this.val === null) {
return;
}
if (this.left) {
this.left.inorder();
}
console.log(this.val);
if (this.right) {
this.right.inorder();
}
};
BinaryTree.prototype.postorder = function () {
'use strict';
if (this.val === null) {
return;
}
if (this.left) {
this.left.postorder();
}
if (this.right) {
this.right.postorder();
}
console.log(this.val);
};
BinaryTree.prototype.size = function () {
'use strict';
var tsize = 0;
if (!this.val) {
return tsize;
}
if (this.val) {
tsize = tsize + 1;
}
if (this.right) {
tsize = tsize + this.right.size();
}
if (this.left) {
tsize = tsize + this.left.size();
}
return tsize;
};
BinaryTree.prototype.minValue = function () {
'use strict';
if (!this.val) {
return;
}
var minValue = this.val;
if (this.left) {
minValue = this.left.minValue();
}
return minValue;
};
BinaryTree.prototype.maxValue = function () {
'use strict';
if (!this.val) {
return;
}
var maxValue = this.val;
if (this.right) {
maxValue = this.right.maxValue();
}
return maxValue;
};
BinaryTree.prototype.lookup = function (num) {
'use strict';
if (!this.val) {
return -1;
}
if (num === this.val) {
return 1;
}
if (num > this.val) {
if (this.right) {
return this.right.lookup(num);
}
} else if (num < this.val) {
if (this.left) {
return this.left.lookup(num);
}
}
return -1;
};
BinaryTree.prototype.hasPathSum = function (sum, nodes) {
'use strict';
if (!this.val) {
return;
}
var csum = 0;
csum = sum - this.val;
if (csum === 0) {
if (!this.right && !this.left) {
nodes.push(this.val);
console.log(nodes.join("->"));
nodes = [];
}
} else if (csum > 0) {
nodes.push(this.val);
if (this.right) {
this.right.hasPathSum(csum, nodes);
nodes.pop();
}
if (this.left) {
this.left.hasPathSum(csum, nodes);
nodes.pop();
}
} else {
return;
}
};
BinaryTree.prototype.printPaths = function (paths) {
'use strict';
if (!this.val) {
return;
}
paths.push(this.val);
if (!this.left && !this.right) {
console.log(paths.join("->"));
paths = [];
} else {
if (this.left) {
this.left.printPaths(paths);
paths.pop();
}
if (this.right) {
this.right.printPaths(paths);
paths.pop();
}
}
};
BinaryTree.prototype.mirror = function () {
'use strict';
if (!this.val) {
return;
}
if (this.right && this.left) {
var temp;
temp = this.right;
this.right = this.left;
this.left = temp;
} else {
if (this.left && !this.right) {
this.right = this.left;
this.left = null;
}
if (this.right && !this.left) {
this.left = this.right;
this.right = null;
}
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment