← Back to DSA Course | Chapter 11: Trees | Lesson 8 of 10

Lowest Common Ancestor ढूँढना

Lowest common ancestor एक family tree में दो cousins द्वारा shared सबसे करीबी grandparent ढूंढने जैसा है।

In this page:

  1. LCA Idea
  2. BST LCA
  3. Binary Tree LCA
  4. Ancestor Paths
  5. LCA Practice
Syntax
markup 
def lca(node, a, b):
    if node is None or node.value == a or node.value == b:
        return node
    left = lca(node.left, a, b)
    right = lca(node.right, a, b)
    if left and right:
        return node
    return left or right

LCA Idea

दो nodes का lowest common ancestor (LCA) tree का सबसे गहरा node है जिसके दोनों descendants हैं — यह वह point है जहां root से हर target node तक paths नीचे trace करने पर अलग होते।

उदाहरण: LCA Idea

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    cout << "LCA of 3 and 8 is 5: the deepest node that has both as descendants" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("LCA of 3 and 8 is 5: the deepest node that has both as descendants");
    }
}
print("LCA of 3 and 8 is 5: the deepest node that has both as descendants")
#include <stdio.h>
int main() {
    printf("LCA of 3 and 8 is 5: the deepest node that has both as descendants\n");
    return 0;
}

BST LCA

Specifically एक binary search tree में, ordering rule LCA ढूंढना तेज़ बनाता है: root से शुरू करते हुए, अगर दोनों targets current node से छोटे हों, left move करें; अगर दोनों बड़े हों, right move करें; पहला node जहां targets अलग sides पर हों (या खुद node से match करें) LCA है।

उदाहरण: BST LCA

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
Node* lca(Node* n, int p, int q) {
    if (p < n->val && q < n->val) return lca(n->left, p, q);
    if (p > n->val && q > n->val) return lca(n->right, p, q);
    return n;
}
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    cout << "LCA(3,8) = " << lca(&root, 3, 8)->val << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static Node lca(Node n, int p, int q) {
        if (p < n.val && q < n.val) return lca(n.left, p, q);
        if (p > n.val && q > n.val) return lca(n.right, p, q);
        return n;
    }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3); root.right = new Node(8);
        System.out.println("LCA(3,8) = " + lca(root, 3, 8).val);
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def lca(n, p, q):
    if p < n.val and q < n.val:
        return lca(n.left, p, q)
    if p > n.val and q > n.val:
        return lca(n.right, p, q)
    return n

root = Node(5)
root.left = Node(3); root.right = Node(8)
print("LCA(3,8) =", lca(root, 3, 8).val)
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
struct Node* lca(struct Node* n, int p, int q) {
    if (p < n->val && q < n->val) return lca(n->left, p, q);
    if (p > n->val && q > n->val) return lca(n->right, p, q);
    return n;
}
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    printf("LCA(3,8) = %d\n", lca(&root, 3, 8)->val);
    return 0;
}

Binary Tree LCA

BST ordering rule के बिना एक general binary tree में, आप value comparisons पर भरोसा नहीं कर सकते — इसके बजाय, standard approach recursively दोनों subtrees search करता है, और वह node जहां हर subtree में एक target मिलती है LCA है।

उदाहरण: Binary Tree LCA

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
Node* lca(Node* n, int p, int q) {
    if (!n || n->val == p || n->val == q) return n;
    Node* l = lca(n->left, p, q);
    Node* r = lca(n->right, p, q);
    if (l && r) return n;
    return l ? l : r;
}
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    cout << "General binary tree LCA(3,8) = " << lca(&root, 3, 8)->val << endl;
    return 0;
}
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static Node lca(Node n, int p, int q) {
        if (n == null || n.val == p || n.val == q) return n;
        Node l = lca(n.left, p, q);
        Node r = lca(n.right, p, q);
        if (l != null && r != null) return n;
        return l != null ? l : r;
    }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3); root.right = new Node(8);
        System.out.println("General binary tree LCA(3,8) = " + lca(root, 3, 8).val);
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def lca(n, p, q):
    if n is None or n.val == p or n.val == q:
        return n
    l = lca(n.left, p, q)
    r = lca(n.right, p, q)
    if l and r:
        return n
    return l if l else r

root = Node(5)
root.left = Node(3); root.right = Node(8)
print("General binary tree LCA(3,8) =", lca(root, 3, 8).val)
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
struct Node* lca(struct Node* n, int p, int q) {
    if (!n || n->val == p || n->val == q) return n;
    struct Node* l = lca(n->left, p, q);
    struct Node* r = lca(n->right, p, q);
    if (l && r) return n;
    return l ? l : r;
}
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    printf("General binary tree LCA(3,8) = %d\n", lca(&root, 3, 8)->val);
    return 0;
}

Ancestor Paths

एक alternative approach root से हर target node तक पूरा path explicitly record करता है, फिर सबसे गहरा common node ढूंढने के लिए दो paths compare करता है — ज़्यादा memory-intensive लेकिन कभी-कभी reason करने में clearer।

उदाहरण: Ancestor Paths

#include <iostream>
#include <vector>
using namespace std;
struct Node { int val; Node *left, *right; };
bool findPath(Node* n, int target, vector<int>& path) {
    if (!n) return false;
    path.push_back(n->val);
    if (n->val == target) return true;
    if (findPath(n->left, target, path) || findPath(n->right, target, path)) return true;
    path.pop_back();
    return false;
}
int main() {
    Node l={3,nullptr,nullptr}, r={8,nullptr,nullptr};
    Node root={5,&l,&r};
    vector<int> path;
    findPath(&root, 3, path);
    cout << "Path to 3: ";
    for (int v : path) cout << v << " ";
    return 0;
}
import java.util.*;
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static boolean findPath(Node n, int target, List<Integer> path) {
        if (n == null) return false;
        path.add(n.val);
        if (n.val == target) return true;
        if (findPath(n.left, target, path) || findPath(n.right, target, path)) return true;
        path.remove(path.size() - 1);
        return false;
    }
    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3); root.right = new Node(8);
        List<Integer> path = new ArrayList<>();
        findPath(root, 3, path);
        System.out.println("Path to 3: " + path);
    }
}
class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def find_path(n, target, path):
    if n is None:
        return False
    path.append(n.val)
    if n.val == target:
        return True
    if find_path(n.left, target, path) or find_path(n.right, target, path):
        return True
    path.pop()
    return False

root = Node(5)
root.left = Node(3); root.right = Node(8)
path = []
find_path(root, 3, path)
print("Path to 3:", path)
#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
int path[10], pathLen = 0;
int findPath(struct Node* n, int target) {
    if (!n) return 0;
    path[pathLen++] = n->val;
    if (n->val == target) return 1;
    if (findPath(n->left, target) || findPath(n->right, target)) return 1;
    pathLen--;
    return 0;
}
int main() {
    struct Node l={3,NULL,NULL}, r={8,NULL,NULL};
    struct Node root={5,&l,&r};
    findPath(&root, 3);
    printf("Path to 3: ");
    for (int i = 0; i < pathLen; i++) printf("%d ", path[i]);
    return 0;
}

LCA Practice

LCA problems कहीं भी दिखती हैं जहां एक hierarchical relationship को एक 'closest common point' answer चाहिए — file system directories, organizational charts, version control history, और biological family trees सभी naturally trees के रूप में model होते हैं जहां LCA questions मायने रखते हैं।

उदाहरण: LCA Practice

#include <iostream>
using namespace std;
int main() {
    cout << "LCA appears anywhere a hierarchy needs a closest-common-point answer: file paths, org charts, version control" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        System.out.println("LCA appears anywhere a hierarchy needs a closest-common-point answer: file paths, org charts, version control");
    }
}
print("LCA appears anywhere a hierarchy needs a closest-common-point answer: file paths, org charts, version control")
#include <stdio.h>
int main() {
    printf("LCA appears anywhere a hierarchy needs a closest-common-point answer: file paths, org charts, version control\n");
    return 0;
}
Related Topics

Longest Common Subsequence क्या है · सामान्य Bit Tricks · Tree की Height और Diameter · Tree Views यानि Left, Right, Top, Bottom

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. एक general binary tree पर BST shortcut (values compare करना) उपयोग करना, जो गलत results देता है।
  2. वह case handle न करना जहां एक node दूसरे का ancestor है।
  3. दोनों subtrees में match मिलने पर current node return करने के बजाय गलती से nullptr return करना।
🔒

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson Height and Diameter of Tree Next Lesson → Tree Views Left Right Top Bottom

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.