Created
May 31, 2020 16:15
-
-
Save dlmanning/5b005f080dc2aeed0fdf5d8e8636f78b to your computer and use it in GitHub Desktop.
Pre and post order traversal without recursion
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
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