1

I saw a good explanation about refactoring of binary tree in-Order traverse function (from recursive to iterative): https://stackoverflow.com/a/2116755/12744612

But I can't refactor Post-order traverse. Can someone explain me in depth like the guy in that link, how can I do it using only one stack? I can do it with two stacks. So, are there any ways to do it with one stack only?

const traverse = (node) => {
    if (node !== null) {
        traverse(node.left);
        traverse(node.right);
        res.push(node.value);
    }
}

My solution with 2 stacks: 

const tempStack = [];
const stack = [];
const res = [];
let node;

if (this.root !== null) {
    tempStack.push(this.root);
}

while (tempStack.length) {
    node = tempStack.pop();
    stack.push(node.value);

    if (node.left !== null) tempStack.push(node.left);
    if (node.right !== null) tempStack.push(node.right);
}
while (stack.length) {
    node = stack.pop();
    res.push(node);
}
return res;
ggorlen
  • 44,755
  • 7
  • 76
  • 106
Spawni
  • 83
  • 4
  • The linked answer contains only a single stack. Why did you come up with two stacks? – plasmacel Feb 19 '20 at 22:29
  • @plasmacel sure. I want to know how implement Post-order method like the guy did that in the link with In-order method using one stack – Spawni Feb 19 '20 at 22:32
  • 1
    Take a look at https://stackoverflow.com/questions/1294701/post-order-traversal-of-binary-tree-without-recursion – ggorlen Feb 19 '20 at 22:39

0 Answers0