Aug 222012

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); }

### 11 Responses to “Lowest Common Ancestor in Binary Search Tree”

Comments (11)

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].

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)

In the Algorithm part, IF (value_at_root < a AND value_at_root < b) and ELSE should be switched

it should return 5

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