In a Binary Search Tree, you are given the values of two nodes. Write a code which will return the Lowest Common Ancestor of both the nodes.
For Example: If the BST is as shown on the right and Nodes are 4 and 8,
The output should be: 5
4 and 8 has two common ancestors 5 and 10. But the lowest one is 5.
Solution:
Lowest Common Ancestor will be the Node which is ancestor to the nodes and whose value lies between the two nodes.
For any two nodes in a BST, there is one and only one common ancestor whose value will be between the two nodes (i.e less than one and greater than the other).
Algorithm:
FUNCTION FindCommonAncestor(Node * root, int a, int b)
IF (value_at_root < a AND value_at_root > b) OR (value_at_root < b AND value_at_root < a)
RETURN root
ELSE
IF (value_at_root < a AND value_at_root < b)
RETURN FindCommonAncestor(root->left_sub_tree, a, b)
ELSE
RETURN FindCommonAncestor(root->right_sub_tree, a, b)
Code:
/**
* Return the Least Common Ancestor (LCA) of Nodes with values a and b
*/
Node* commonAncestor(Node* root, int a, int b)
{
// case when LCA doesn't exist
if(root == NULL || root->data == a || root->data == b)
return NULL;
if( (root->data > a && root->data < b) || (root->data > b && root->data < a) )
return root;
// LCA will be on the LEFT sub-tree
if(root->data > a && root->data > b)
return commonAncestor(root->lptr, a, b);
// LCA will be on the RIGHT sub-tree
if(root->data < a && root->data < b)
return commonAncestor(root->rptr, a, b);
}
Does this algorithm work?
For a = 1 and b = 4 it returns NULL instead 5.
Sorry, the correct question should be:
Does this algorithm work?
For a = 1 and b = 4 it returns NULL instead 4.
it should return 5
Actually it can be debated and should be defined.. And that’s how it should be during the interview.. We should ask the interviewer what does he expect in such cases..
You are right.. will need to put a check that if data of node == either a or b then stop there and return that
pls correct it
it create lots of confusion
what in case of a=1 and b=4
can a node be ancestor of its own
what wl be the ancestor of a=1 and b=4
it should return 5
In the Algorithm part, IF (value_at_root < a AND value_at_root < b) and ELSE should be switched
Shouldn't the first IF statement of the Algorithm be:
IF (value_at_root < a AND value_at_root > b) OR (value_at_root > a AND value_at_root < b)
public void listar(int valorClave1, int valorClave2)throws IOException, volcará por la salida
estándar la información de los registros del archivo de datos cuyo campo numReg se encuentre
en el intervalo [valorClave1, valorClave2] (ambos inclusive), ordenados por el campo numReg.
En la implementación de este método se deberá evitar visitar páginas del árbol B que con toda
seguridad NO contienen claves que se encuentren dentro del intervalo [valorClave1,
valorClave2].
This line
IF (value_at_root b) OR (value_at_root < b AND value_at_root < a)
RETURN root
should be like
IF (value_at_root b) OR (value_at_root a)
RETURN root