Microsoft Interview Question
SDETsTeam: Cloud
Country: United States
Here is my solution in C# assuming the tree is binary tree.
Regarding the max number of elements in stack at a time - height of the binary tree. Assuming the binary tree is balanced, it is log(n) where n is number if elements in the tree.
public static void InOrderWithoutStack(Node root)
{
if (root == null)
throw new ArgumentNullException("root");
Node temp = root;
Stack<Node> s = new Stack<Node>();
while (temp != null)
{
s.Push(temp);
temp = temp.Left;
}
while (s.Count != 0)
{
Node t = s.Pop();
System.Console.WriteLine(t.Value + " ");
if (t.Right != null)
{
t = t.Right;
while (t != null)
{
s.Push(t);
t = t.Left;
}
}
}
}
1) I am assuming this is a Binary Tree to begin with
A simple non recursive (Iterative) approach is possible by trying to replace the recursion stack by our own stack, sort of a behavioral replication. Here are the steps:
a) Keep adding all the left nodes to the stack.
b) Once done with step 'a', pop the element from the stack and print it.
c) Once done with step 'b', add the node on the right of the popped element to the stack.
d) Repeat 'a','b','c' until the stack is empty & there are no elements left on the right.
The maximum size of the stack in the worst case would be O(n) as the height of the BT could be 'n' in the worst case.
Here's the java code:
/*
* Given the root of a BT. We must print the
* Inorder of this tree without recursion.
* The solution is O(n) time and O(n) space
* solution
*/
public void printInorderIterative(TreeNode root)
{
if(root==null)
return;
Stack<TreeNode> s= new Stack<TreeNode>();
TreeNode current= root;
while(!s.isEmpty() || current!=null)
{
while(current!=null)
{
s.push(current);
current=current.left;
}
if(!s.isEmpty())
{
current=s.pop();
System.out.print(current.element + " ");
current=current.right;
}
}
}
public static void nonrecursiveInorder(Node root) {
Stack<Node> queue = new Stack<>();
if (root == null)
throw new NullPointerException();
else {
queue.add(root);
while (!queue.isEmpty()) {
Node _temp = new Node();
_temp = queue.pop();
if (_temp.leftChild == null && _temp.rightChild == null) {
System.out.println(_temp.data);
} else {
if (_temp.visited == false) {
if (_temp.rightChild != null)
queue.add(_temp.rightChild);
queue.add(_temp);
_temp.visited = true;
if (_temp.leftChild != null)
queue.add(_temp.leftChild);
} else {
System.out.println(_temp.data);
}
}
}
}
}
public static void InOrderTreeTraversal(TreeNode rootNode)
{
var treeStack = new Stack<TreeNode>();
treeStack.Push(rootNode);
while (treeStack.Count != 0)
{
var currentNode = treeStack.Pop();
if (currentNode != null &&
(currentNode.Left != null || currentNode.Right != null))
{
if (currentNode.Right != null) treeStack.Push(currentNode.Right);
treeStack.Push(currentNode);
treeStack.Push(null);
if (currentNode.Left != null) treeStack.Push(currentNode.Left);
}
else
{
if (currentNode == null && treeStack.Count > 0)
currentNode = treeStack.Pop();
Console.Write("{0} ", (char)currentNode.Data);
}
}
}
void print(node *root, int N) {
node* stk[N];
int stkSize=1,num[N];
stk[1]=root;
num[1]=0;
while (stkSize) {
root=stk[stkSize];
if (root==NULL) {
stkSize--;
continue;
}
if (num[stkSize]==0) {
num[stkSize]++;
stkSize++;
stk[stkSize]=root->left;
num[stkSize]=0;
}
else if (num[stkSize]==1) {
printf("%d ",root->val);
num[stkSize]++;
stkSize++;
stk[stkSize]=root->right;
num[stkSize]=0;
}
else if (num[stkSize]==2) stkSize--;
}
}
void print(node *root)
{
stack st;
if(root) st.push(root);
while(!st.empty())
{
if (root->left)
{
st.push(root->left);
root = root->left;
continue;
}
print st.top();
pop();
while (!root->right)
{
//Backtrace
print st.top();
root = st.pop();
}
if(root->right)
{
st.push(root->right)
root
}
if (root->right)
{
st.push(root->right)
root = root->right
}
}
}
Here's the simple C# code for both recursive and iterative in-order traversals. The maximum stack size is equal to the tree height. For an arbitrary tree it is equal to O(n) in the worst case. For a perfectly balanced BST it is equal to O(lgN).
- stanislav.khalash January 24, 2015