Finding LCA in a binary tree using Recursion
To find the Lowest Common Ancestor of node A and node B do
- Recursively traverse downwards the left sub-tree and right sub-tree of root.
- Return matching node A, node B, or null to every parent node at the upper level.
- If the nodes returned to a parent from the recursive traversal are node A and node B
- then the parent node is the lowest common ancestor.
Example: We have to find the lowest common ancestor of node 1 and node 13.
As we recurse downwards in the left-subtree, data of the leaf node 1 matches with the data of node 1, hence
- Node 1 returns node 1 to the parent node 3.
- Node 3 returns node 1 to parent node 5.
- Node 5 returns node 1 to parent node 9.
Similary As we recurse downwards, data of the leaf node 13 matches with the data of node 13, hence
- Node 13 returns node 13 to the parent node 15.
- Node 15 returns node 13 to parent node 18.
- Node 18 returns node 13 to parent node 16.
- Node 16 returns node 13 to parent node 9.
Note: Data of leaf nodes 7, 12 and 20 doesn’t match with the data of node 1 or node 13 hence each returns Null to the parent.
As the left sub-tree and the right sub-tree of the root (9) has node 1 and node 13 respectively, root (9) has to be the lowest common ancestor of node 1 and node 13.
Algorithm: GetLCA ( Root, Node A, Node B )
If ( Root == Null or Root.Data == (Node A).Data or
Root.Data == (Node B).Data ) then
return Root
LCA_From_Left = GetLCA ( Root.Left, Node A, Node B )
LCA_From_Right = GetLCA ( Root.Right, Node A, Node B )
If (LCA_From_Left != Null and LCA_From_Right != Null ) then
return Root
If ( LCA_From_Left == Null )
return LCA_From_Right
Else
return LCA_From_Left
Time complexity : O ( N ), where ‘N’ is the number of nodes in the tree. As this algorithm uses tree traversal like post-order where every node is visited only once, it gives us the time complexity of O ( N ).
Program for recursively finding the Lowest Common Ancestor (LCA) in a binary tree
#include <iostream>
#include <stack>
using namespace std;
class Node{
public:
Node(int n): data(n), left(nullptr), right(nullptr) { }
Node(int n, Node * arg_left, Node * arg_right): data(n), left(arg_left), right(arg_right) { }
Node * left;
Node * right;
int data;
};
Node * GetLCA (Node * root, Node * p, Node * q) {
if (root == nullptr || root->data == p->data || root->data == q->data)
return root;
Node * left_lca = GetLCA (root->left, p, q);
Node * right_lca = GetLCA (root->right, p, q);
if (left_lca && right_lca)
return root;
if (left_lca == NULL)
return right_lca;
else
return left_lca;
}
/* Constructed binary tree is
9
/ \
5 16
/ \ / \
3 7 12 18
/ / \
1 15 20
/
13
*/
int main() {
Node node_1(1, nullptr, nullptr);
Node node_7(7, nullptr, nullptr);
Node node_12(12, nullptr, nullptr);
Node node_13(13, nullptr, nullptr);
Node node_20(20, nullptr, nullptr);
Node node_15(15, &node_13, nullptr);
Node node_3(3, &node_1, nullptr);
Node node_18(18, &node_15, &node_20);
Node node_5(5, &node_3, &node_7);
Node node_16(16, &node_12, &node_18);
Node root(9, &node_5, &node_16);
cout << "LCA of (1, 13) : " << GetLCA(&root, &node_1, &node_13)->data << endl;
cout << "LCA of (3, 7) : " << GetLCA(&root, &node_3, &node_7)->data << endl;
cout << "LCA of (12, 20) : " << GetLCA(&root, &node_12, &node_20)->data << endl;
cout << "LCA of (15, 18) : " << GetLCA(&root, &node_15, &node_18)->data << endl;
return 0;
}
Output
LCA of (1, 13) : 9
LCA of (3, 7) : 5
LCA of (12, 20) : 16
LCA of (15, 18) : 18