Cisco Systems Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
public static void postOrderTraversalIterative(Node root)
{
if (root == null) return;
Stack<Node> s = new Stack<Node>();
s.Push(root);
Node prev = null;
while (s.Count > 0)
{
Node curr = s.Peek();
// we are traversing down the tree
if (prev == null || prev.Left == curr || prev.Right == curr)
{
if (curr.Left != null)
{
s.Push(curr.Left);
}
else if (curr.Right != null)
{
s.Push(curr.Right);
}
else
{
Console.WriteLine(curr.Data);
s.Pop();
}
}
// we are traversing up the tree from the left
else if (curr.Left == prev)
{
if (curr.Right != null)
{
s.Push(curr.Right);
}
else
{
Console.WriteLine(curr.Data);
s.Pop();
}
}
// we are traversing up the tree from the right
else if (curr.Right == prev)
{
Console.WriteLine(curr.Data);
s.Pop();
}
prev = curr; // record previously traversed node
}
}
/* Iterative function for inorder tree traversal */
void inOrder(struct tNode *root)
{
/* set current to root of binary tree */
struct tNode *current = root;
struct sNode *s = NULL; /* Initialize stack s */
bool done = 0;
while (!done)
{
/* Reach the left most tNode of the current tNode */
if(current != NULL)
{
/* place pointer to a tree node on the stack before traversing
the node's left subtree */
push(&s, current);
current = current->left;
}
/* backtrack from the empty subtree and visit the tNode
at the top of the stack; however, if the stack is empty,
you are done */
else
{
if (!isEmpty(s))
{
current = pop(&s);
printf("%d ", current->data);
/* we have visited the node and its left subtree.
Now, it's right subtree's turn */
current = current->right;
}
else
done = 1;
}
} /* end of while */
}
// An iterative process to print preorder traversal of Binary tree
void iterativePreorder(node *root)
{
// Base Case
if (root == NULL)
return;
// Create an empty stack and push root to it
stack<node *> nodeStack;
nodeStack.push(root);
/* Pop all items one by one. Do following for every popped item
a) print it
b) push its right child
c) push its left child
Note that right child is pushed first so that left is processed first */
while (nodeStack.empty() == false)
{
// Pop the top item from stack and print it
struct node *node = nodeStack.top();
printf ("%d ", node->data);
nodeStack.pop();
// Push right and left children of the popped node to stack
if (node->right)
nodeStack.push(node->right);
if (node->left)
nodeStack.push(node->left);
}
}
// An iterative function to do post order traversal of a given binary tree
void postOrderIterative(struct Node* root)
{
// Create two stacks
struct Stack* s1 = createStack(MAX_SIZE);
struct Stack* s2 = createStack(MAX_SIZE);
// push root to first stack
push(s1, root);
struct Node* node;
// Run while first stack is not empty
while (!isEmpty(s1))
{
// Pop an item from s1 and push it to s2
node = pop(s1);
push(s2, node);
// Push left and right children of removed item to s1
if (node->left)
push(s1, node->left);
if (node->right)
push(s1, node->right);
}
// Print all elements of second stack
while (!isEmpty(s2))
{
node = pop(s2);
printf("%d ", node->data);
}
}
using stack:
- gs July 17, 2012PreOrder:
push root
while(stack != empty)
{
pop node
print node
if node->right
push node->right
if node->left
push node->left
}