Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Pre and post order traversal without recursion
class Stack extends Array {
top() {
return this[this.length - 1];
}
size() {
return this.length;
}
}
class Node {
constructor(label) {
this.label = label;
this.children = [];
}
addChildren(...args) {
this.children.push(...args);
}
toString() {
return this.label;
}
pre(depth) {
let indent = '';
for (let i = 0; i < depth; i++) indent += ' ';
console.log(`${indent}${this.label}: Pre`);
}
post(depth) {
let indent = '';
for (let i = 0; i < depth; i++) indent += ' ';
console.log(`${indent}${this.label}: Post`);
}
}
let a = new Node('A');
let b = new Node('B');
let c = new Node('C');
let d = new Node('D');
let e = new Node('E');
let f = new Node('F');
let g = new Node('G');
let h = new Node('H');
let i = new Node('I');
let j = new Node('J');
f.addChildren(b, g);
b.addChildren(a, d);
d.addChildren(c, e, j);
g.addChildren(i);
i.addChildren(h);
let stack = new Stack();
let parent_stack = new Stack();
stack.push(f);
while (stack.length > 0) {
let current = stack.pop();
if (current === parent_stack.top()) {
// If this node is the top of the parent stack, we're exiting from it.
// Remove it from the parent stack and do the post-order visit
parent_stack.pop();
current.post(parent_stack.size());
} else {
// Otherwise this we're entering this node, do the pre-order visit
current.pre(parent_stack.size());
if (current.children.length > 0) {
// Does this node have children? If so, push it back on the stack
// for its post-visitation, then all queue-up all its children
// Also add it to the parent stack since the next loop will be in its children.
stack.push(current, ...current.children.reverse());
parent_stack.push(current);
} else {
// Otherwise this is a leaf node, go ahead and do its post-order visitation now.
current.post(parent_stack.size());
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment