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

Lowest Common Ancestor

The lowest common ancestor is like finding the closest grandparent shared by two cousins in a family tree.

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

The lowest common ancestor (LCA) of two nodes is the deepest node in the tree that has both of them as descendants — it's the point where the paths from the root to each target node would split apart if traced downward.

Example: 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

In a binary search tree specifically, the ordering rule makes LCA fast to find: starting at the root, if both targets are smaller than the current node, move left; if both are larger, move right; the first node where the targets fall on different sides (or match the node itself) is the LCA.

Example: 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

In a general binary tree without the BST ordering rule, you can't rely on value comparisons — instead, the standard approach recursively searches both subtrees, and the node where one target is found in each subtree is the LCA.

Example: 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

An alternative approach explicitly records the full path from the root to each target node, then compares the two paths to find the deepest node they still have in common — more memory-intensive but sometimes clearer to reason about.

Example: 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 appear anywhere a hierarchical relationship needs a 'closest common point' answer — file system directories, organizational charts, version control history, and biological family trees are all naturally modeled as trees where LCA questions make sense.

Example: 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 · Common Bit Tricks · Height and Diameter of Tree · 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. #}
Common Mistakes
  1. Using the BST shortcut (compare values) on a general binary tree, which gives wrong results.
  2. Not handling the case where one of the nodes is the ancestor of the other.
  3. Returning nullptr incorrectly when both subtrees find a match instead of returning the current node.
🔒

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.