How about traversing from one node to root, adding each node to hashset, Then try do the same with second one, on collision return node.

View Allnum of num

Software Development Engineer In Test Interview Seattle, WA

Amazon## Most of them were expected. Almost all are problem solving

questions. 1. Given a BST with following property find the LCA of two given nodes. Property : All children has information about their parents but the parents do not have information about their children nodes. Constraint - no additional space can be used

Tags:

problem solving See More, See Less8

15 Answers

▲

1

▼

How about traversing from one node to root, adding each node to hashset, Then try do the same with second one, on collision return node.

▲

1

▼

No, you cannot do that since you need extra space for hashset which is not allowed, I am going to post my solution in a min

▲

7

▼

function findLCA(Node node1, Node node2)

{

int counter1 = 0;

int counter2 = 0;

Node temp;

//Find the level for each node, use a temp node to

//traverse so that we don't lose the info for node 1 and node 2

temp = node1;

while( temp.parent ! = null)

{

temp = temp.parent;

counter1++;

}

temp = node2;

while( node2.parent ! = null)

{

node2 = node2.parent;

counter2++;

}

/*

* We wanna make them at the same level first

*/

if(counter1 > counter2)

{

while(counter1 != counter2)

{

node1 = node1.parent;

counter1--;

}

}

else

{

while(counter2 != counter1)

{

node2 = node2.parent;

counter2--;

}

}

while (node1.parent != node2.parent)

{

node1 = node1.parent;

node2 = node2.parent;

}

System.out.println("Found the LCA: " + node1.parent.info);

}

▲

3

▼

//correction

temp = node2;

while( temp.parent ! = null)

{

temp = temp.parent;

counter2++;

}

▲

0

▼

@chmielsen : your solution would work... but as said by Hamid, due to the constraint of space, you have to consider some other technique.

▲

0

▼

I seems really like the question of finding intersection of two linked lists

▲

0

▼

1)consider node1 as p1. see if p1=p2 , p1->parent=p2, p2->parent=p1

2)now for a value p1 try to see recursively if p2->parent ever becomes equal to p1 or p2=root

3)set p1=p1->parent and continue till p1=p2 or p1= root

▲

0

▼

temp1 = node1;

temp2 = node2;

while( temp1.parent != null && temp2.parent != null){

if(temp1.value == temp2.value){

return temp1; // temp1 and temp2 point to same node so pick one

}

temp1 = temp1.parent;

temp2 = temp2.parent;

}

System.out.println("no such ancestor");

▲

1

▼

Consider this is a BST, where max node is always on the right of min node, we can traverse max upward one node at a time while comparing min nodes as it traverse upward toward root.

BinaryNode findBSTLCA( BinaryNode min, BinaryNode max ) {

BinaryNode tempMax = max;

BinaryNode tempMin = min;

while( tempMax != null ) {

while( tempMin != null ) {

if( tempMin.element == tempMax.element )

return tempMin;

tempMin = tempMin.parent;

}

tempMin = min; // reset tempMin

tempMax = tempMax.parent; // traverse tempMax upward 1 node

}

return null; // no LCA found

}

▲

1

▼

Consider that the lowest common ancestor in a binary search tree means the node value would be between the two values passed in. Because everything left is less than and everything right is greater than, we can traverse the tree using this knowledge.

Here's the solution in PHP for something different:

function findLowestCommonAncestor(Node $root, $value1, $value2)

{

while ($root != null)

{

$value = $root->getValue();

if ($value > $value1 && $value > $value2)

{

$root = $root->getLeft();

}

else if ($value getRight();

}

else

{

return $root;

}

}

return null; //the tree is empty

}

▲

0

▼

howardkhl - your solution works, but this is O(n^2) complexity, making it too slow for large enough trees.

Ja - your solution might work (haven't thoroughly checked it) but it violates the restriction that a parent node does not know about the child node. So this answer is invalid.

The correct answer is the one given by Hamid Dadkhah, which, just like an anonymous responsder said, is the same problem as an intersecting list.

▲

0

▼

you can use the following method

*Node getLCA(Node *n1, Node* n2){

while(n1.parent!=null){

Node * p= n2;

while(p.parent!=null){

if(n1.parent!=p.parent)

p=p.parent;

else

return p.parent;

}

}

}

▲

0

▼

Pick one of the nodes in random. Keep traversing up until the property: new node is greater than one of the nodes and lesser than the other is satisfied.

▲

0

▼

I was also interviewed with same question. They not only ask the solution they also ask for the time complexity of the solution. Make sure you to ask different questions and confirm the type of tree. They could give you binary search tree, binary tree, sorted binary tree. Solution will greatly depend on the type of the tree.

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

Hint - detect the level at which the given nodes are present. Then travel upwards from that position.