﻿ Find least common ancestor (lca) of 2 nodes in a binary search tree ~ Programming Tutorials by SourceTricks
Friday, July 13, 2012

## Find least common ancestor (lca) of 2 nodes in a binary search tree

### Write a program to find least common ancestor (lca) of 2 nodes in a binary search tree

The approach:-
1. Starting from the root node.

2. Check if the node key is between the two provided keys. If so, the current node is the least common ancestor.

3. If the two provided keys are greater than the current node then recursively search the right sub-tree.

4. If the two provided keys are less than the current node then recursively search the left sub-tree.

#### C++ program to find least common ancestor (lca) of 2 nodes in a binary search tree

```#include <iostream>
#include <cstdlib>
using namespace std;

// Node class
class Node {
public:
Node() { mData = -1; mParent = NULL; mLeft = NULL; mRight = NULL; }
~Node() {}
int data() { return mData; }
void setData(int data) { mData = data; }
Node* left() { return mLeft; }
void setLeft(Node* left) { mLeft = left; }
Node* right() { return mRight; }
void setRight(Node* right) { mRight = right; }
Node* parent() { return mParent; }
void setParent(Node* parent) { mParent = parent; }
private:
int mData;
Node* mLeft;
Node* mRight;
Node* mParent;
};

// Tree class
class Tree {
public:
Tree() { mRoot = NULL; }
~Tree() {}
Node* root() { return mRoot; }
Node* lca(Node* node, int data1, int data2);

private:

private:
Node* mRoot;
};

if ( mRoot == NULL ) {
Node* tmp = new Node();
tmp->setData(data);
mRoot = tmp;
}
else {
}
}

void Tree::addNode(Node* node, int data) {
if ( data <= node->data() ) {
if ( node->left() != NULL )
else {
Node* tmp = new Node();
tmp->setData(data);
tmp->setParent(node);
node->setLeft(tmp);
}
}
else {
if ( node->right() != NULL )
else {
Node* tmp = new Node();
tmp->setData(data);
tmp->setParent(node);
node->setRight(tmp);
}
}
}

Node* Tree::lca(Node* node, int data1, int data2) {
if ( node ) {
int data = node->data();
if ( data1 < data && data2 > data )
return node;
else if ( data1 > data && data2 > data )
return lca(node->right(), data1, data2);
else
return lca(node->left(), data1, data2);
}
return NULL;
}

// Test program
int main() {
Tree* t = new Tree();

cout << t->lca(t->root(), 150, 350)->data() << endl;

delete t;
}```

Output:-
`300`

Name

Email *

Message *