🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
The Lowest Common Ancestor (LCA) of two nodes n1 and n2 is defined as the lowest node in the tree that has both n1 and n2 as descendants. In this post, we will explore a C++ program to find the LCA in a binary tree.
2. Program Overview
Our approach involves a recursive traversal of the binary tree. As we traverse down from the root, if one of the nodes matches either n1 or n2, we return the node's pointer. Otherwise, we search in both the left and right subtrees. If both left and right subtree calls return non-NULL values, it indicates that the current node is the LCA. If only one subtree call returns non-NULL, then that return value is the LCA.
3. Code Program
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(NULL), right(NULL) {}
};
Node* findLCA(Node* root, int n1, int n2) {
if (!root) return NULL;
// If either n1 or n2 matches with the root's key, report the presence
if (root->data == n1 || root->data == n2) {
return root;
}
// Look for n1 and n2 in left and right subtrees
Node* left_lca = findLCA(root->left, n1, n2);
Node* right_lca = findLCA(root->right, n1, n2);
// If n1 and n2 are found in left and right subtrees of the current node, then it's the LCA
if (left_lca && right_lca) return root;
// Otherwise, check if the left subtree or right subtree is LCA
return (left_lca != NULL) ? left_lca : right_lca;
}
int main() {
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
int n1 = 4, n2 = 5;
Node* lca = findLCA(root, n1, n2);
cout << "LCA of " << n1 << " and " << n2 << " is: " << lca->data << endl;
return 0;
}
Output:
LCA of 4 and 5 is: 2
4. Explanation
The findLCA function recursively traverses the tree, and for each node, it checks if either of the input nodes matches with it. If it does, it returns the node. If not, it checks the left and right subtrees. If both left and right subtree calls have non-NULL return values, it means this current node is the LCA. Otherwise, we return whichever non-NULL value we get from the left or right subtree calls, indicating the LCA lies on that side.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment