ProgramGuru

Lowest Common Ancestor (LCA) in a Binary Tree

Problem and examples

Given a binary tree and two nodes (p and q), find their lowest common ancestor (LCA). The LCA of two nodes p and q in a binary tree is defined as the lowest node in the tree that has both p and q as descendants (where a node can be a descendant of itself).

Input Tree Node 1 Node 2 LCA Description
[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4] 5 1 3 LCA is 3 — the lowest node with both 5 and 1 in its subtrees
[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4] 6 4 5 LCA is 5 — 6 and 4 lie in the left subtree of 5
[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4] 7 8 3 LCA is 3 — 7 is in left subtree, 8 is in right subtree of root
[1, 2] 1 2 1 LCA is 1 — root node is the ancestor of 2
[1, 2, 3, 4, 5, 6, 7] 4 5 2 LCA is 2 — both nodes are in the left subtree
[1, 2, 3, 4, 5, 6, 7] 4 6 1 LCA is 1 — nodes are in opposite subtrees of root
[1] 1 1 1 LCA is 1 — node is the ancestor of itself
[] 1 2 null Tree is empty — no LCA can be found

How it works

Understanding the Problem

We are given a binary tree and two distinct nodes, p and q. Our task is to find their Lowest Common Ancestor (LCA). The LCA is the deepest node in the tree that has both p and q as descendants (where a node can be a descendant of itself).

This problem is important in understanding tree structures and recursive thinking. For beginners, think of LCA as the “fork” in the tree where the paths to p and q split. We’ll solve this step-by-step using a real example and cover all possible cases.

Step-by-Step Solution with Example

Step 1: Analyze the Tree Structure

Let’s consider the following binary tree:

        3
       /       5   1
     /  /     6  2 0  8
      /      7   4

Suppose we need to find the LCA of nodes 5 and 1.

Step 2: Understand the Path to Each Node

Path to node 5: 3 → 5

Path to node 1: 3 → 1

The first common node from the root downwards is 3. So, the LCA is 3.

Step 3: Recursive Intuition

We use a recursive function that does the following:

  • If the current node is null, return null.
  • If the current node is either p or q, return the current node.
  • Recursively search left and right subtrees.
  • If both left and right return non-null, current node is the LCA.
  • If only one side is non-null, propagate it upwards.

Step 4: Java Code for LCA

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    if (left != null && right != null) return root;

    return (left != null) ? left : right;
}

Step 5: Explanation for Beginners

We search down both subtrees. If both subtrees return a match, then the current node is where the paths to p and q diverge — this is the LCA. If only one subtree returns a match, we return that node up the recursive call stack.

Edge Cases

Case 1: Nodes in Different Subtrees

Example: nodes 5 and 1 → LCA is 3. This is the standard scenario.

Case 2: One Node is Ancestor of the Other

Example: nodes 5 and 4 → path is 5 → 2 → 4. Since 5 is an ancestor of 4, LCA is 5.

Case 3: Tree with Only Root and One Child

Example: tree [1,2], nodes 1 and 2 → LCA is 1. Even if the tree is tiny, LCA is still computed correctly.

Case 4: Tree is Empty

Example: tree [] → LCA is null. We should always handle this before running the main logic.

Case 5: p and q Are the Same Node

Example: nodes 2 and 2 → LCA is 2. A node is considered its own ancestor.

Finally

The LCA problem teaches recursive tree traversal and highlights important base conditions. Always understand how the tree is structured, and trace paths for both nodes. Use edge cases during testing to build intuition.

This problem is foundational for solving many other tree-based problems and is a must-know for interviews and practice.

  1. If root is null or equal to p or q, return root.
  2. Recursively search for LCA in the left subtree: left = lowestCommonAncestor(root.left, p, q).
  3. Recursively search for LCA in the right subtree: right = lowestCommonAncestor(root.right, p, q).
  4. If both left and right are non-null, then root is the LCA; return root.
  5. If only one of left or right is non-null, return the non-null value.

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left, *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

int main() {
    TreeNode* root = createNode(3);
    root->left = createNode(5);
    root->right = createNode(1);
    root->left->left = createNode(6);
    root->left->right = createNode(2);
    root->right->left = createNode(0);
    root->right->right = createNode(8);
    root->left->right->left = createNode(7);
    root->left->right->right = createNode(4);

    TreeNode* lca = lowestCommonAncestor(root, root->left->right->left, root->left->right->right);
    printf("LCA: %d\n", lca ? lca->val : -1);
    return 0;
}

C++ implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(5);
    root->right = new TreeNode(1);
    root->left->left = new TreeNode(6);
    root->left->right = new TreeNode(2);
    root->right->left = new TreeNode(0);
    root->right->right = new TreeNode(8);
    root->left->right->left = new TreeNode(7);
    root->left->right->right = new TreeNode(4);

    TreeNode* lca = lowestCommonAncestor(root, root->left->right->left, root->left->right->right);
    cout << "LCA: " << (lca ? lca->val : -1) << endl;
    return 0;
}

Python implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    return left if left else right

# Example usage
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(5)
    root.right = TreeNode(1)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(2)
    root.right.left = TreeNode(0)
    root.right.right = TreeNode(8)
    root.left.right.left = TreeNode(7)
    root.left.right.right = TreeNode(4)

    lca = lowestCommonAncestor(root, root.left.right.left, root.left.right.right)
    print("LCA:", lca.val if lca else None)

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class Main {
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

        TreeNode lca = lowestCommonAncestor(root, root.left.right.left, root.left.right.right);
        System.out.println("LCA: " + (lca != null ? lca.val : "None"));
    }
}

JavaScript implementation

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

function lowestCommonAncestor(root, p, q) {
    if (!root || root === p || root === q) return root;
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

const root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);

const lca = lowestCommonAncestor(root, root.left.right.left, root.left.right.right);
console.log("LCA:", lca ? lca.val : "None");

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
        return root
    }
    if left != nil {
        return left
    }
    return right
}

func main() {
    root := &TreeNode{Val: 3}
    root.Left = &TreeNode{Val: 5}
    root.Right = &TreeNode{Val: 1}
    root.Left.Left = &TreeNode{Val: 6}
    root.Left.Right = &TreeNode{Val: 2}
    root.Right.Left = &TreeNode{Val: 0}
    root.Right.Right = &TreeNode{Val: 8}
    root.Left.Right.Left = &TreeNode{Val: 7}
    root.Left.Right.Right = &TreeNode{Val: 4}

    lca := lowestCommonAncestor(root, root.Left.Right.Left, root.Left.Right.Right)
    if lca != nil {
        fmt.Println("LCA:", lca.Val)
    } else {
        fmt.Println("LCA: None")
    }
}

Rust implementation

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

fn main() {
    println!("Rust version would require lifetimes and Rc for shared ownership. This is a placeholder to show structure.");
}

Kotlin implementation

class TreeNode(val value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
    if (root == null || root == p || root == q) return root
    val left = lowestCommonAncestor(root.left, p, q)
    val right = lowestCommonAncestor(root.right, p, q)
    return if (left != null && right != null) root else left ?: right
}

fun main() {
    val root = TreeNode(3)
    root.left = TreeNode(5)
    root.right = TreeNode(1)
    root.left!!.left = TreeNode(6)
    root.left!!.right = TreeNode(2)
    root.right!!.left = TreeNode(0)
    root.right!!.right = TreeNode(8)
    root.left!!.right!!.left = TreeNode(7)
    root.left!!.right!!.right = TreeNode(4)

    val lca = lowestCommonAncestor(root, root.left!!.right!!.left, root.left!!.right!!.right)
    println("LCA: ${lca?.value}")
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) {
        self.val = val
    }
}

func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
    if root == nil || root === p || root === q {
        return root
    }
    let left = lowestCommonAncestor(root?.left, p, q)
    let right = lowestCommonAncestor(root?.right, p, q)
    if left != nil && right != nil {
        return root
    }
    return left ?? right
}

let root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left?.left = TreeNode(6)
root.left?.right = TreeNode(2)
root.right?.left = TreeNode(0)
root.right?.right = TreeNode(8)
root.left?.right?.left = TreeNode(7)
root.left?.right?.right = TreeNode(4)

if let lca = lowestCommonAncestor(root, root.left?.right?.left, root.left?.right?.right) {
    print("LCA: \(lca.val)")
} else {
    print("LCA: None")
}

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null = null;
    right: TreeNode | null = null;
    constructor(val: number) {
        this.val = val;
    }
}

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
    if (!root || root === p || root === q) return root;
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    if (left && right) return root;
    return left || right;
}

const root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);

const lca = lowestCommonAncestor(root, root.left.right.left!, root.left.right.right!);
console.log("LCA:", lca ? lca.val : "None");