Last active
June 27, 2017 02:54
Star
You must be signed in to star a gist
Binary tree, insert, exists, preorder, postorder, inorder traversal.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Good, thank you. I am reading. I do not need to write it now. Aha.