Problem Statement: Given a binary tree find its post order traversal.
Solution: In post-order traversal of a node’s right child is printed first then its left child and then the node and this order must be valid for all subtrees in the tree. It can be noticed that post-order traversal is reverse of the pre-order traversal of the with right children swaped with left children of the tree.
Following algorithm makes use of stack to first find pre-order traversal iteratively and it treats right child as if it were the left child , this will produce a pre-order traversal which can then be reversed to produce correct post-order traversal of the input tree . We start with having root node at the top of the stack, we drill down the tree rooted at the node at top of stack along the right most side , and output each node we encounter them. We then start poping until we find a node that has a left child. This left child is pushed onto the stack and above procedure gets repeated for subtree rooted at this node. Finally we reverse the traversal to give correct post-order traversal.
Post-Order Tree Traversal (Iterative)526 views
function postorderTraversalIterative(root){
/**
* Node:{val:number,left:Node,right:Node}
* sample input
* var tree={ val:"F",
* left:{ val:"B",
* left:{ val:"A" },
* right:{ val:"D",
* left:{val:"C"},
* right:{val:"E"}
* }
* },
* right:{val:"G",
* right:{ val:"I",
* left:{val:"H"}
* }
* }
* };
*/
function peek(stack){
return stack[stack.length-1];
}
var stack = [root],
output = [],top;
while(stack.length>0){
while(peek(stack).right){
output.push(peek(stack).val);
stack.push(peek(stack).right);
}
output.push(peek(stack).val);
// backup to parent which has a left child
while((top=stack.pop()) && !top.left){}
// if parent was found, then push its left child
if(top){
stack.push(top.left);
}
}
return output.reverse();
}