Coders Packet

Find LCA(Lowest Common Ancestor) in Binary Tree using C++

By Bharat Pandey

Hello coders, Today we will discuss how to find LCA(Lowest Common Ancestor) in a Binary Tree using C++ Programming .

So, Last time we will discuss Binary Tree and its operation in C++. If you don't understand what is a binary tree and how to implement it?  Please check this link -> Implementation of Binary tree Operation in C++.

Q1:  What is LCA(Lowest Common Ancestor)?

Lowest Common Ancestor

The LCA(Lowest Common Ancestor) of any two nodes is the last common node of the path of these two nodes.

In the above tree, the LCA of node d and node e is node b, and the LCA of node f and node e is node a.

Q2: How to find LCA(Lowest Common Ancestor)?

If you observe closely in the above tree or image you figure out the LCA of the given nodes will be the last common node in the paths from the root node to the given nodes.

i.e. LCA of nodes d and e?

The path from the root to the node d is [a, b, d] 

The path from the root to the node e is [a, b, d]

so, the last common node is b. 

Ans: node b is the LCA of nodes d and e.

Steps to Find LCA(Lowest Common Ancestor):

step 1: Find the path from the root node to the first node and store it.

step 2: Find the path from the root node to the second node and store it.

step3: Compare these two paths and the last common node is the LCA(Lowest Common Ancestor).

Note: In source code, if any node is not found in the binary tree nothing will be the output of LCA.

Ok, GoodBye Coders. Hope you understand. 

Download Complete Code

Comments

No comments yet