Epic Systems Interview Question
Software Engineer / DevelopersPlease find the program for iterative post order of a binary tree using two stacks.
One stack(say NodeStack) is for keeping the nodes, the other stack(say FlagStack) is for keeping the flag corresponding to the respective node which is on the NodeStack.
node = root;
while(1)
{
if(node)
{
NodeStack.push(node);
FlagStack.push(false);
node = node->left;
}
else
{
if(NodeStack.isEmpty()) break;
topFlag = FlagStack.pop();
if(topFlag == false)
{
FlagStack.push(true);
node = node->right;
}
else
{
node = NodeStack.pop();
print the node ..
node = NULL;
}
}
}
Note: You may ask me that the above code is using visited flag. Right..!! but here I am not keeping the visited flag in each node of the binary tree which leads to the space complexity of O(N). Here I am using another stack to keep the flags corresponding to the nodes on the first stack.
public void printPostOrderNR() {
BinarayTreeNode node = root;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
if(node != null)
stack.push(node);
while (stack.isempty() == false){
node = stack.peek();
if(node.getVisited()) {
stack.pop();
node.print();
}
else {
node.setVisited();
right = node.getRight();
if(right != null) stack.push(right);
left = node.getLeft();
if(left != null) stack.push(left);
}
}
Can you please let me know, if this was a question from skills assessment test?
- frooty August 27, 2009