Skip to content

Instantly share code, notes, and snippets.

@primaryobjects
Last active June 27, 2017 02:54
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save primaryobjects/90dd4aa532d0449a726e08baa4fdbc56 to your computer and use it in GitHub Desktop.
Binary tree, insert, exists, preorder, postorder, inorder traversal.
var insert = function(value, root) {
if (!root) {
// Create a new root.
root = { val: value };
}
else {
var current = root;
while (current) {
if (value < current.val) {
if (!current.left) {
// Insert left child.
current.left = { val: value };
break;
}
else {
current = current.left;
}
}
else if (value > current.val) {
if (!current.right) {
// Insert right child.
current.right = { val: value };
break;
}
else {
current = current.right;
}
}
else {
// This value already exists. Ignore it.
break;
}
}
}
return root;
}
var exists = function(value, root) {
var result = false;
var current = root;
while (current) {
if (value < current.val) {
current = current.left;
}
else if (value > current.val) {
current = current.right;
}
else {
result = true;
break;
}
}
return result;
}
var traversePre = function(head, callback) {
// Preorder traversal.
if (head) {
if (callback) {
callback(head.val);
}
traversePre(head.left, callback);
traversePre(head.right, callback);
}
}
var traversePost = function(head, callback) {
// Postorder traversal.
if (head) {
traversePost(head.left, callback);
traversePost(head.right, callback);
if (callback) {
callback(head.val);
}
}
}
var traverseIn = function(head, callback) {
// Inorder traversal.
if (head) {
traverseIn(head.left, callback);
if (callback) {
callback(head.val);
}
traverseIn(head.right, callback);
}
}
var traverseInIterative = function(head, callback) {
// Inorder traversal (iterative style).
var current = head;
var history = [];
// Move down to the left-most smallest value, saving all nodes on the way.
while (current) {
history.push(current);
current = current.left;
}
current = history.pop();
while (current) {
if (callback) {
callback(current.val);
}
// Move to the right, and then go down to the left-most smallest value again.
current = current.right;
while (current) {
history.push(current);
current = current.left;
}
current = history.pop();
}
}
var root = insert(10);
insert(5, root);
insert(6, root);
insert(3, root);
insert(20, root);
@shuntaochen
Copy link

Good, thank you. I am reading. I do not need to write it now. Aha.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment