Microsoft Interview Question for SDETs


Team: Cloud
Country: United States




Comment hidden because of low score. Click to expand.
1
of 1 vote

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).

using System;
using System.Collections.Generic;

namespace CareerCup
{
    public class TreeNode
    {
        private readonly int _key;
        private readonly int _value;

        public TreeNode(int key, int value)
        {
            _key = key;
            _value = value;
        }

        public int Key
        {
            get
            {
                return _key;
            }
        }

        public int Value
        {
            get
            {
                return _value;
            }
        }

        public TreeNode Left { get; set; }

        public TreeNode Right { get; set; }
    }

    public class InorderTraversal
    {
        public void TraverseRecursively(TreeNode node, Action<TreeNode> callback)
        {
            if (node == null)
            {
                return;
            }

            TraverseRecursively(node.Left, callback);
            callback(node);
            TraverseRecursively(node.Right, callback);
        }

        public void TraverseIteratively(TreeNode node, Action<TreeNode> callback)
        {
            if (node == null)
            {
                return;
            }

            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (stack.Count > 0 || node != null)
            {
                if (node == null)
                {
                    TreeNode parent = stack.Pop();
                    callback(parent);
                    node = parent.Right;
                }
                else
                {
                    stack.Push(node);
                    node = node.Left;
                }
            }
        }
    }
}

- stanislav.khalash January 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the question restricts to no recursion solutions

- albinoadriano February 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
                    }
                }
            }
        }

- Victor January 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
			}
		}
	}

- teli.vaibhav January 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This algorithm will not work as when you reach the left most node, the current will be assigned to null in the last line current = current.right and you will break out of the while look.

- Sam February 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
					}
				}
			}
		}
	}

- ankit.vader February 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
                }
            }
        }

- asiful mahfuze February 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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--;

    }
}

- Ivan March 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}
}
}

- Vaibhav Gupta April 19, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More