Microsoft Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
I guess the tree is not BST, because if it is, the problem becomes finding the first node in BST which is in the middle of two nodes, this is O(log N).
This can be done in O(n), the same question I hv done in Amz .
Algo here.
1> Trace the path of node one from the root to child and store all the values in an array1. O(n).
2> Trance the path of node two from the root to child and store all the values in array 2. O (n).
Now U gotto check Index by Index in array 1 and array 2. Just before first index that mismatched is the common ancestor.
Total Time is . O(n)+O(n)+ O(n) = 3*O(n) ~O(n)..
Remember assuming the tree is completely unordered we requires O(n) coz we are assuming its flat out. else if we hv any pattern we can utilize the same..
This is not an optimized solution you are using extra memory . There has been no constraint mentioned in the question but this solution can be optimized of course.
Here is an approach
public TreeNode LCAHelp(TreeNode root, TreeNode a, TreeNode b)
{
bool checka = false;
bool checkb = false;
if(!checka && !checkb)
Node LCA = LCAHelp(root,a,b,ref checka, ref check b);
}
if (checka || checkb)
{
Node validated = LCAHelp(root,a,b,ref checka, ref check b);
}
if (checka && checkb)
return LCA;
else
return null;
public TreeNode LCAHelp(TreeNode root, TreeNode a, TreeNode b, ref bool checka, ref bool checkb)
{
if(root == null){
return null;
}
if(root == a && checka= false){
return root;
}
if(root == b && checkb= false){
return root;
}
TreeNode leftSide = LCAHelp(root.left, a, b);
TreeNode rightSide = LCAHelp(root.right, a, b);
if(leftSide!=null && rightSide!=null){
return root;
}
return leftSide==null?rightSide:leftSide;
}
}
if we have access to the parent of each node .. we can go up in the tree and then see where the 2 arrays of parents intersect. Instead of an array we will use hashmaps to store the parents. O(n) complexity
Thats not an option.. Coz the question clearly says it binary Tree.. So we DON'T have any extra pointer
Class Solution{
public TreeNode LCA(TreeNode root, TreeNode a, TreeNode b){
if(root == null){
return null;
}
if(root == a || root == b){
return root;
}
TreeNode leftSide = LCA(root.left, a, b);
TreeNode rightSide = LCA(root.right, a, b);
if(leftSide!=null && rightSide!=null){
return root;
}
return leftSide==null?rightSide:leftSide;
}
}
Find out whether the two nodes are in the left of root, right of root or one in left and other in right.
If (on left)------ call the same function for (root->l)
if(on right)----- call the same function for (root->r)
if(on different)--return root.
This will take O(n).
Why would this be O(n)? because i see that this will repeatedly traverse nodes down the same path over and over until you diverge?
Class Solution{
public TreeNode LCA(TreeNode root, TreeNode a, TreeNode b){
if(root == null){
return null;
}
if(root == a || root == b){
return root;
}
TreeNode leftSide = LCA(root.left, a, b);
TreeNode rightSide = LCA(root.right, a, b);
if(leftSide!=null && rightSide!=null){
return root;
}
return leftSide==null?rightSide:leftSide;
}
}
I think it is a classic problem in career cup.
The solution is: (assumption is we have the parent pointer)
1. keep move up both nodes by using parent pointer, and keep 2 counters.
after both of them reach the root. Then we have the two counters that
stores the steps which the node need to move to root.
2. By this we can get the difference between two counters. then move up the
larger-counter node only with the different steps. Finally, move both nodes
step by step, when they meet, that is the common ancestor.
Any problem with this method? or the time complexity is bad?
I think it is possible to solve the problem with O(lgn) with extra memory and parent pointer. Here is the solution
TNode *LCA(TNode *u, TNode *v)
{
stack <TNode *> us, vs;
TNode *tmp_u= u, *tmp_v=v, *tmp_lca=NULL;
while (tmp_u->getParent()!=NULL)
{
us.push(tmp_u->getParent());
tmp_u=tmp_u->getParent();
}
while (tmp_v->getParent()!=NULL)
{
vs.push(tmp_v->getParent());
tmp_v=tmp_v->getParent();
}
while((us.empty()!=true) && ((vs.empty()!=true)) && (us.top()==vs.top()))
{
tmp_lca=us.top();
us.pop();
vs.pop();
}
return tmp_lca;
}
Following is a solution in O(n) running time.
1. If Node A is a parent of Node B, return Node A regardless if Node B exists, and visa-versa.
2. If node A/B not found, return null.
3. Else, do LCS.
Disclaimer: this is rather tricky to do in an in-person interview without a debugger ;o)
static Node findLCA(final Node root, final Node nodeA, final Node nodeB,final SearchResult searchResult)
{
/**
* base case
*/
boolean foundA=false,foundB=false;
if(root==null || nodeA==null || nodeB==null)return null;
else if(nodeA==nodeB)return nodeA;
if(searchResult.node!=null && searchResult.foundA && searchResult.foundB)
{
return searchResult.node;
}
else if(root.equals(nodeA) || root.equals(nodeB))
{
return root;
}
if(root.left!=null)
{
Node foundNode = findLCA(root.left,nodeA,nodeB,searchResult);
if(searchResult.node!=null && searchResult.foundA && searchResult.foundB)return searchResult.node;
else if(foundNode!=null)
{
foundA=foundA||foundNode.equals(nodeA);
foundB=foundB||foundNode.equals(nodeB);
}
if(foundA && foundB)
{
searchResult.node=root;
searchResult.foundA=true;
searchResult.foundB=true;
return root;
}
}
if(root.right!=null)
{
Node foundNode = findLCA(root.right,nodeA,nodeB,searchResult);
if(searchResult.node!=null && searchResult.foundA && searchResult.foundB)return searchResult.node;
else if(foundNode!=null)
{
foundA=foundA||foundNode.equals(nodeA);
foundB=foundB||foundNode.equals(nodeB);
}
if(foundA && foundB)
{
searchResult.node=root;
searchResult.foundA=true;
searchResult.foundB=true;
return root;
}
}
if(foundA)
return nodeA;
else if(foundB)
return nodeB;
else
return null;
}
static class SearchResult
{
Node node;
boolean foundA,foundB;
}
static class Node implements Comparable<Node>{
Node left;
Node right;
Integer value;
public int compareTo(Node o) {
return value.compareTo(o.value);
}
public boolean equals(Object o){
Node target = (Node)o;
return this.compareTo(target)==0;
}
public String toString()
{
return "Node("+value+")";
}
}
Stupid method:
public TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q){
if(covers(root.left,p) && covers(root,q)){
return commonAncestor(root.left, p , q);
}
if(covers(root.right, p) && covers(root.right, q)){
return commonAncestor(root.right, p , q);
}
return root;
}
public boolean covers(TreeNode root, TreeNode n){
if(root == null){
return null;
}
if(root == n){
return true;
}
return covers(root.left,n) || covers(root.right,n);
}
smart method(O(n)):
static int NO_NODES_FOUND = 0;
static int ONE_NODES_FOUND = 1;
static int TWO_NODES_FOUND = 2;
public int covers(TreeNode root, treeNode p, TreeNode q){
int ret = NO_NODES_FOUND;
if(root == null){
return ret;
}
if(root == p || root == q){
ret += 1;
}
ret += covers(root.left,p,q);
if(ret == TWO_NODES_FOUND){
return ret;
}
return ret+covers(root.right,p,q);
}
public TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q){
if( (p == q) && (root.left == p || root.right == q)){
return root;
}
int nodesFromLeft = covers(root.left,p,q);
if(nodesFromLeft == TWO_NODES_FOUND){
if(root.left == p || root.left == q){
return root.left;
}else{
return commonAncestor(root.left,p,q);
}
}else if(nodesFromLeft == ONE_NODES_FOUND){
if(root == p){
return p;
}else if(root == q){
return q;
}
}
int nodesFromRight = covers(root.right,p,q);
if(nodesFromRight == TWO_NODES_FOUND){
if(root.right == p || root.right == q){
return root.right;
}else{
return commonAncestor(root.right,p,q);
}
}else if(nodesFromRight == ONE_NODES_FOUND){
if(root == p){
return p;
}else if(root == q){
return q;
}
}
if(nodesFromLeft == ONE_NODES_FOUND && nodesFromRight == ONE_NODES_FOUND){
return root;
}else{
return null;
}
}
if you are sure that the numbers(data) exists in tree, then the following algorithm works in short time.
int common_ancestor2(node *n,int n1,int n2)
{
node *t=n;
while(t!=NULL)
{
if(t->data >n1 && t->data >n2)
t=t->left;
else if (t->data <n1 && t->data <n2)
t=t->right;
else
return t->data;
}
return -1;
}
With Some modification, we can continue further till elements found. By the time elements found, we are already found the common ancestor.
Modified version is here, which returns common ancestor only when the two elements exists in the tree.
// Logic is if both moves left, continue
// If both moves right continue
// If one moves left and the other moves right then thats the Ancestor.
// NO Additional space is required.
int common_ancestor3(node *t,int n1,int n2)
{
node *l,*r;
while(t!=NULL)
{
if(t->data >n1 && t->data >n2)
t=t->left;
else if (t->data <n1 && t->data <n2)
t=t->right;
else
break;
}
// We are at junction, then find out existence of elements
r=l=t;
while(l!=NULL)
{
if(n1>l->data)
l=l->right;
else if ( n1 < l->data)
l=l->left;
else
break;
}
while(r!=NULL)
{
if(n2>r->data)
r=r->right;
else if ( n2 < r->data)
r=r->left;
else
break;
}
// If any one of elements is not found
// There is no point in returning the found ancestor - Dont be fool
if ( l == NULL || r== NULL )
return -1;
return t->data;
}
struct node * getLCABT(struct node *root,int a,int b)
{
struct node *l;
struct node *r;
if(!root)return NULL;
if(root->data == a || root->data==b)
{
return root;
}
l = getLCABT(root->lc,a,b);
r = getLCABT(root->rc,a,b);
if(l!=NULL && r!=NULL)return root;
else if(l!=NULL){
return l;
//return getLCABT(root->lc,a,b);
}
else{
return r;
//getLCABT(root->rc,a,b);
}
}
If the tree is BST, we may use Breath-first search approach.
Here is JavaScript solution:
find: function(node, value1, value2) {
var queue = [node];
var index = 0;
var found1 = false;
var found2 = false;
var ancestorIndex;
while (index < queue.length) {
node = queue[index];
if (!found1 && node.value === value1) {
found1 = true;
if (typeof ancestorIndex == 'undefined') {
ancestorIndex = index - 1;
}
}
else if (!found2 && node.value === value2) {
found2 = true;
if (typeof ancestorIndex == 'undefined') {
ancestorIndex = index - 1;
}
}
if (found1 && found2) {
return queue[ancestorIndex].value;
}
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
++index;
}
return null;
}
Let's have tree with these values:
5, 3, 1, 0 , 2, 4
Ancestor of 1, 2 -> 3
Ancestor of 3, 4 -> 5
- Vir Pratap Uttam May 04, 2015private static BinaryTreeNode LCA(BinaryTreeNode root, BinaryTreeNode alpha, BinaryTreeNode beta) { BinaryTreeNode left,right; if(root==null) return root; if(root.getData()==alpha.getData() || root .getData()==beta.getData()) return root; left=LCA(root.getLeft(),alpha,beta); right=LCA(root.getRight(),alpha,beta); if(left!=null && right!=null) return root; else return left!=null?left:right; }