Problem: Given a binary tree, find its pre-order traversal without using recursion.
Solution: In pre-order traversal of a tree root of tree is printed first then its left child 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 pre-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 , and output each node we encounter them. We then start poping 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.
Pre-Order Traversal (Iterative)283 views
/**
* preorder travesal of binary tree
* @param {Node} root
* @return {Array} values in preorder
*/
function preorderTraversalIterative(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){
output.push(peek(stack).val);
stack.push(peek(stack).left);
}
output.push(peek(stack).val);
// backup to parent which has a right child
while((top=stack.pop()) && !top.right){} // empty loop
// if parent was found, then push its right child
if(top) {
stack.push(top.right);
}
}
return output;
}