## Microsoft Interview Question for SDE1s

Country: United States
Interview Type: In-Person

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

Is it possible to get the solution this way ?
Get the path from root to node a and b. (Use 2 stacks)
And start popping the node out until you find a common node.

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

Yes, this solution should work in O(N), and can be done using a single stack.
do a pre-order of the first node, and Push every node in the stack.
Now take the second node, do the same Pre-order traversal, and this time visiting every node do a POP from the stack if the Popped value doesn't match with the current node value then the last Pop value was the lowest common ancestor.

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

Suppose if node a is parent of node b, what should be the output?

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

node a

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

This can't be done in O(n) without extra space.
Down voting can't change the facts

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

Algo:
At any node, check if either of its children or both of its children has return true (got keys)
i) if both elements are found, then this current node is common ancestor. return current node
ii) if either of children has return true and this current node is another key then return this current node
iii) if either of children has return true & this current node is not another key, return NULL but update found pointer with true.

Function is called :
found = 0;
tree* node = commonAncestor (root, &found, f, s)

``````tree *commonAncestor (tree *root, int *found, int f, int s)
{
if (!root)
return NULL;

if (root->key == f && root->key == s)
{
*found = 1;
return root;
}

if (root->key == f || root->key == s)
{
*found = 1;
}

int left = 0;
int right = 0;

tree *ret = common (root->left, &left, f, s);
if (ret != NULL)
return ret;

ret = common (root->right, &right, f, s);
if (ret != NULL)
return ret;

if (left == 1 && right == 1)
{
*found = 1;
return root;
}

else if (left == 1 || right == 1)
{
if (*found == 1)
return root;
*found = 1;
return NULL;
}
return NULL;
}``````

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

time complexity will be O(n) as in worst case we will have to visit all nodes of the tree.
Space complexity will be O(log n) which is required for recursion.

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

Is it only a Binary Tree or a Binary Search Tree(BST) ?

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

Least common Ancestor Tested this code

``````struct BinaryTreeNode *LCA(struct BinaryTreeNode *root,struct BinaryTreeNode  *a,struct BinaryTreeNode *b) {
struct BinaryTreeNode *left,*right;
if (root == NULL) return NULL;
if(root == a || root == b) return root;
left = LCA(root->left,a,b)
right = LCA(root->right,a,b)
if(left && right)
return root;
else
return (left? left:right)
}``````

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

In this code, if node a or node b doesn't exist, it returns the node that exists.

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

It looks like the last line should be return null instead of return (left? left:right)

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

@anonymous: if node a or node b doesn't exist
if (root == NULL) return root;
it returns NULL after travelling the entire tree...

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

``````static int findLowestCommonAncestor(final TreeNode node, int first, int second){
if((node.getValue() < first) == (node.getValue() < second)){
return findLowestCommonAncestor(node.getValue() < first ? node.getRight() : node.getLeft(), first, second);
} else if(node.getValue() == first || node.getValue() == second){
return node.getValue() == first ? first : second;
} else
return node.getValue();
}``````

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

Its not BST just Binary tree

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

In a binary tree, there is no way to avoid O(n^2)

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

This problem can ben solved in O(N), and using a single stack.
do a pre-order of the first node, and Push every node in the stack.
Now take the second node, do the same Pre-order traversal, and this time visiting every node do a POP from the stack if the Popped value doesn't match with the current node value then the last Pop value was the lowest common ancestor.
Note: we need another variable to hold the last matched node.

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

``````bool findLCA(Node* node, int minC, int valA, int valB)
{
if(!node) return MAXINT;

minC = min(node->val, minC);

bool bFoundL = findLCA(node->left, minC, valA, valB);
bool bFoundR = findLCA(node->right, minC, valA, valB);
if(bFoundL && bFoundR)
{
printf("Lowest Common Ancestor is: %d", minC);
return false;
}

return bFoundL || bFoundR || node->val == valA || node->val == valB;
}

// call like this
findLCA(root, MAXINT, value1, value2);``````

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.