Skip to content

Instantly share code, notes, and snippets.

@thomasvaeth
Created September 20, 2018 22:38
Show Gist options
  • Save thomasvaeth/93d4c3389ed757b97d88a377b7b400ae to your computer and use it in GitHub Desktop.
Save thomasvaeth/93d4c3389ed757b97d88a377b7b400ae to your computer and use it in GitHub Desktop.
function Node(data) {
this.data = data;
this.left = null;
this.right = null;
}
function BST() {
this.root = null;
}
BST.prototype.push = function(data) {
var current = this.root;
if (!current) {
this.root = new Node(data);
return;
}
var node = new Node(data);
while (current) {
if (data < current.data) {
if (!current.left) {
current.left = node;
break;
} else {
current = current.left;
}
} else {
if (!current.right) {
current.right = node;
break;
} else {
current = current.right;
}
}
}
};
function postOrder(root) {
var current = root,
stack = [],
completed = false;
while (!completed) {
if (current) {
if (current.right) stack.push(current.right);
stack.push(current);
current = current.left;
} else {
if (stack.length) {
current = stack.pop();
if (current.right && stack[stack.length - 1] === current.right) {
stack.pop();
stack.push(current);
current = current.right;
} else {
console.log(current.data);
current = null;
}
} else {
completed = true;
}
}
}
}
var binarySearchTree = new BST();
binarySearchTree.push(6);
binarySearchTree.push(4);
binarySearchTree.push(8);
binarySearchTree.push(2);
binarySearchTree.push(5);
binarySearchTree.push(7);
binarySearchTree.push(9);
binarySearchTree.push(1);
binarySearchTree.push(3);
postOrder(binarySearchTree.root);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment