Problem Statement: Given a binary tree find its inorder traversal.
Solution: In In-order traversal of a tree left child of any node is printed first then the node itself and then its right child and this order must be valid for all subtrees in the tree.
Following algorithm makes use of stack to find in-order traversal iteratively. 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 left most side , when we reach the left most node we output it. We then start poping and outputting the node until we find a node that has a right child. This right child is pushed onto the stack and above procedure gets repeated for subtree rooted at this node.
In-Order Tree Traversal (Iterative)278 views
function inorderTraversalIterative(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).left){
stack.push(peek(stack).left);
}
output.push(peek(stack).val);
// backup to parent which has a right child
while((top=stack.pop()) && !top.right){
if(stack.length>0){
output.push(peek(stack).val);
}
}
// if parent was found, then push its right child
if(top){
stack.push(top.right);
}
}
return output;
}