Interview Question

Country: United States

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

``````int Depth(Node* n1)
{
int depth = 0;
while (n1->parent)
{
++depth;
n1 = n1->parent;
}
return depth;
}

Node* CommonAncestor(Node* n1, Node* n2)
{
int d1 = Depth(n1);
int d2 = Depth(n2);

if (d1 > d2)
{
while (d1 != d2)
{
--d1;
n1 = n1->parent;
}
}
else if (d2 > d1)
{
while (d1 != d2)
{
--d2;
n2 = n2->parent;
}
}

//Now they are on same level...
while (n1 != n2)
{
n1 = n1->parent;
n2 = n2->parent;
}

return n1;		//or n2
}``````

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

The solution provided here assume that there is a parent pointer, but it's a working solution. +1

If there are no parent pointers;
LCA(A, B)
1. Get inorder list from (A, B).
1.2. If there are no elements between inorder (A, B), then return the latter
1.3 else
1.3.a. Check the order of each element in (A,B) in post-order
1.3.b. Return the highest order element in postorder, which is the LCA

e.g., LCA(10, 40)
inorder : 10 20 30 40 80
postorder : 10 30﻿ 20 80 40
then LCA(10, 40) = 20

O(n) time, O(n) space

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

you said if theres no elements in between during the inorder traversal to post the latter as the ancestor but what if the tree is like this
10 i think your explanation assumes this: 40
\ /
40 10

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

``````public boolean isAncestor(Node ancestor, Node child) {
if(ancestor == null || child == null) {
return false;
}
Node parent = child;

while(parent != null) {
if(parent = ancestor) {
return true;
}
parent = parent.getParent();
}
return false;
}

public Node getCommonAncestor(Node node1, Node node2) {
if(isAncestor(node1, node2)) {
return node1;
} else if(isAncestor(node2, node1)) {
return node2;
} else {
if(node1 == null || node2 == null) {
return null;
} else {
Node parent = node1.getParent();
while(parent != null) {
if(isAncestor(parent, node2)) {
return parent;
}
parent = parent.getParent();
}
return null;
}
}
}``````

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

Woops,

if (parent == ancestor)

not

if (parent = ancestor)

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

Good solution...

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

Assuming that we have nodes containing info1 and info2 present inside the BST

``````public BTreeNode<T> leastCommonParent(BTreeNode<T> node,T info1,T info2){

BTreeNode<T> node1 = new BTreeNode<T>(info1);
BTreeNode<T> node2 = new BTreeNode<T>(info2);

//return null if node==null
if(node==null){
return null;
}

if(node.getLeft()!=null){
if(node.getLeft().compareTo(node1)==0 || node.getLeft().compareTo(node2)==0){
return node;
}
}
if(node.getRight() !=null){
if(node.getRight().compareTo(node1)==0 || node.getRight().compareTo(node2)==0){
return node;
}
}

if(node.compareTo(node1)>0 && node.compareTo(node2)>0){

return leastCommonParent(node.getLeft(), info1, info2);
//return node;

}
else if(node.compareTo(node1)<0 && node.compareTo(node2)<0){

return leastCommonParent(node.getRight(), info1, info2);

}else{

return node;

}

}``````

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.