Last active
June 27, 2017 02:54
-
-
Save primaryobjects/90dd4aa532d0449a726e08baa4fdbc56 to your computer and use it in GitHub Desktop.
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.