## Microsoft Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

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

``````node* lowestInLevel(node* current) {
int level = 0;
node* root = current;
while(root->parent != null) {
root = root->parent;
level++;
}
return findleftmostatlevel(root,level);
}
node * findleftmostatlevel(node * root,int level)
{
if(level == 0)
return root;
if(!root->left && !root->right)
return NULL;
node * temp = findleftmostatlevel(root->left,level-1);
if(temp)
return temp;
else
return findleftmostatlevel(root->right,level-1);``````

}

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

I was also asked same Question week back by Microsoft but for rightside node....use level order traversal using queue

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

Interviewer also asked me to solve it without using queue/level order traversal by assuming each node hash PARENT pointer

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

Assuming that the total number of elements is N, we must avoid trying to go to the left because we will achieve O (N) running time. Instead, first i would find the root and in the same time i would count my depth level. Then i would try to traverse down by trying to peek on each step the most left node. This down traversal i would do until my depth is reached. Total running time would be O (log N)

Comment hidden because of low score. Click to expand.
0

But that is not O(log N) in worst or average case. It is O(log N) in the best case only, although I do agree DFS is better on average than BFS.

In worst case the tree is linear and your node can be the last.

In general, your tree can still be inbalanced and you may have to traversal n/2 or n/3 nodes to find the answer.

Comment hidden because of low score. Click to expand.
0

O (Log N) it's NOT the best case, it's the average case. The best case is O (1) if the tree is plat (all nodes has a single root, the root of the tree) and I have to perform only two steps to find out the left most node.

Comment hidden because of low score. Click to expand.
0

The worst case will be O(N) because you are not travelling only path. Suppose first time you chose the left node but the depth of the node is h-2 that means the if your input node is in height h then you should chose the right node first.The way you solve is using recursion. That will end up using O(N) in worst case.

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

how will you print the nodes on the same level as you don't have the root node? Is additional information missing such as the node also have pointer to the parent node?

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

``````public void lowestInLevel(Node current) {
int level = 0;
Node runner = current;
while(runner.parent != null) {
runner = runner.parent;
level++;
}
int i = 0;
while(count != i) {
if(runner.left != null)
runner = runner.left;
else
runner = runner.right;
i++;
}
System.out.println(runner);
}``````

Comment hidden because of low score. Click to expand.
0

Hey..this will break if left subtree has height 3 and right subtree has height 5 and the input node is depth 5 node. Your loop will never go to depth 5.

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

``````public void lowestInLevel(Node current) {
int level = 0;
Node runner = current;
while(runner.parent != null) {
runner = runner.parent;
level++;
}
int i = 0;
while(count != i) {
if(runner.left == null && runner.right == null)
throw new NoSuchElementException();
else if(runner.left != null)
runner = runner.left;
else
runner = runner.right;
i++;
}
System.out.println(runner);
}``````

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

node* lowestInLevel(node* current) {
int level = 0;
node* root = current;
while(root->parent != null) {
root = root->parent;
level++;
}
return findleftmostatlevel(root,level);
}
node * findleftmostatlevel(node * root,int level)
{
if(level == 0)
return root;
if(!root->left && !root->right)
return NULL;
node * temp = findleftmostatlevel(root->left,level-1);
if(temp)
return temp;
else
return findleftmostatlevel(root->right,level-1);
}

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

node* lowestInLevel(node* current) {
int level = 0;
node* root = current;
while(root->parent != null) {
root = root->parent;
level++;
}
return findleftmostatlevel(root,level);
}
node* findleftmostatlevel(node * root,int level)
{
if(level == 0)
return root;
if(!root->left && !root->right)
return NULL;
node * temp = findleftmostatlevel(root->left,level-1);
if(temp)
return temp;
else
return findleftmostatlevel(root->right,level-1);
}

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

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace ConsoleApplication45
{
class Program
{
static void Main(string[] args)
{
// data for creating tree
// This file contains a string of numbers separated by spaces
string[] input_data = File.ReadAllText(@"G:\input.txt").Split(new char[] { ' ','\n','\r','\t'}, StringSplitOptions.RemoveEmptyEntries);
if (input_data.Length == 0)
{
return;
}
Tree node = new Tree(); // creating of root
// creating of tree
for (int i =0; i< input_data.Length; i++)
{
// this case is needed to fill the root
{
node.data = int.Parse(input_data[i]);
}
else
{
node = GrowingTree(node, int.Parse(input_data[i]));
}
}
// Now we have a tree for test
// Get node for test
int test_counter =2;
while (node != null && test_counter > 0)
{
node = node.right;
test_counter--;
}
node = GetLeftMost(node);
}
static Tree GetLeftMost(Tree item)
{
int level = 0;
if (item == null)
{
return null;
}
// Get root
while (item.parent !=null)
{
item = item.parent;
level++;
}
// Get left most
while (level > 0)
{
// Left sub tree is not null
if (item.left != null)
{
item = item.left;
level--;
}
// Get right sub tree
else {
item = item.right;
level--;
}
}

return item;
}
static Tree GrowingTree(Tree node, int data)
{
if (node.data > data)
{
if (node.left != null)
{
GrowingTree(node.left, data);
}
else
{
node.left = new Tree(node, data);

}
}
else
{
if (node.right != null)
{
GrowingTree(node.right, data);
}
else
{
node.right = new Tree(node, data);
}
}
return node;
}
}
class Tree
{
public Tree parent;
public Tree left;
public Tree right;
public int data;
// Constructors
public Tree()
{ }
public Tree(Tree in_parent, int in_data)
{
data = in_data;
parent = in_parent;
}
}
}``````

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

Worst case time complexity will be O(N) (for any type of a tree: complete binary tree (i.e. a heap), full binary tree, balanced or unbalanced tree, binary search tree, full binary tree etc.).

Universal solution:

1. Find the depth/height of the pointed node in the tree.

2. Perform a pre-order traversal over the tree. We return the first node we obtain at the depth/height obtained in the step 1.

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

``````public Node findLeftMost(int data) {
while (!q.isEmpty()) {
Node temp = q.poll();
if (temp != null) {
if (temp.leftNode != null) {
if (temp.leftNode.nData == data)
return temp.leftNode;
else {
}
}
if (temp.rightNode != null) {
{
if (temp.rightNode.nData == data) {
return temp.leftNode;
} else {
}
}
}
}
}
return null;
}``````

Comment hidden because of low score. Click to expand.
0

with the tree..if you send 6 to your function it return Node 6. That is not what is expected from this question
1
/ \
2 3
/ \ / \
4 5 6 7

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

c# implementation.

``````private static Node Find( Node node ) {

if ( node.Parent != null ) {
_counter = _counter + 1 ?? 1;
return Find( node.Parent );
}

return InOrder( node );
}

private static Node InOrder( Node node ) {

if ( _counter == 0 || _counter == null ) {
return node;
}

if ( node.LeftChild != null && !Visited.Contains( node.LeftChild ) ) {
_counter--;
return InOrder( node.LeftChild );
}

if ( node.RightChild != null && !Visited.Contains( node.RightChild ) ) {
_counter--;
return InOrder( node.RightChild );
}
_counter++;
return InOrder( node.Parent );
}

static readonly HashSet<Node> Visited = new HashSet<Node>();
private static int? _counter = null;``````

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

void display_same_level(struct btree **b) {
deque< struct btree* > dtree;

if(*b)
dtree.push_back(*b);
int level=0;
int element_at_level=1;
while(!dtree.empty() ) {
struct btree* t = dtree.front();
cout << t->nodedata << " " ;
dtree.pop_front();
element_at_level--;
if(element_at_level == 0) {
level++;
}
if(t->left) {
dtree.push_back(t->left);
element_at_level++;
}
if(t->right) {
dtree.push_back(t->right);
element_at_level++;
}
}
}

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

First track the level of the node and add parent pointer in your tree structure.

``````static void LeftMostNodeSameLevel(Node myNode)
{
int level = 0;
while (myNode.Parent!=null)
{
myNode = myNode.Parent;
level += 1;
}

while (myNode!=null && level>0)
{
if (myNode.LeftNode != null)
myNode = myNode.LeftNode;
else
myNode = myNode.RightNode;

level-=1;
}

Console.WriteLine("Left Most Node is {0}",myNode.Value);
}``````

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

``````public static string leftmostNode(Node n)
{
if (n == null)
{
return null;
}
if (n != null && n.left == null)
{
return n.data.ToString();
}

return leftmostNode(n.left);
}``````

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

``````public static string leftmostNode(Node n)
{
if (n == null)
{
return null;
}
if (n != null && n.left == null)
{
return n.data.ToString();
}

return leftmostNode(n.left);``````

}

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.

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