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

Lowest Common Ancestor

In this page:

  1. LCA Idea
  2. BST LCA
  3. Binary Tree LCA
  4. Ancestor Paths
  5. LCA Practice

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;
}
🔒

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.