Microsoft Interview Question
SDE1sCountry: United States
Interview Type: In-Person
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.
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;
}
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)
}
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();
}
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.
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);
Is it possible to get the solution this way ?
- Anonymous May 05, 2013Get the path from root to node a and b. (Use 2 stacks)
And start popping the node out until you find a common node.