Lowest Common Ancestor of a Binary Tree - Practice Coding Problems

Lowest Common Ancestor of a Binary Tree - Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q in the tree.

According to the definition of LCA: "The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself)."

Note: All node values are unique, and both p and q exist in the tree.

Input & Output

Example 1 — Basic Tree

$ Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

› Output: 3

💡 Note: The LCA of nodes 5 and 1 is 3. Node 3 is the root and both 5 and 1 are in different subtrees.

Example 2 — Ancestor Relationship

$ Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

› Output: 5

💡 Note: The LCA of nodes 5 and 4 is 5. Node 4 is a descendant of node 5, so 5 is their lowest common ancestor.

Example 3 — Two Node Tree

$ Input: root = [1,2], p = 1, q = 2

› Output: 1

💡 Note: In a two-node tree, the root is always the LCA of both nodes.

Constraints

The number of nodes in the tree is in the range [2, 10⁵]
-10⁹ ≤ Node.val ≤ 10⁹
All Node.val are unique
p ≠ q
p and q will exist in the tree

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes p and q to find LCA

Search Process

Traverse tree to find lowest node containing both targets

LCA Found

Return the lowest common ancestor node

Key Takeaway

🎯 Key Insight: The LCA is the deepest node where paths to both targets diverge

Asked in

f Facebook 78 a Amazon 65 M Microsoft 52 G Google 48

The recursive DFS approach is optimal - it uses post-order traversal to identify the LCA in a single pass. The key insight is that when we find both target nodes in different subtrees of a node, that node must be their LCA. Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive DFS	O(n)	O(h)	Single traversal that returns LCA when both nodes found in different subtrees
Path Storage Approach	O(n)	O(h)	Store paths from root to both nodes, then find the last common node

Recursive DFS — Algorithm Steps

Recursively search left and right subtrees
If current node is p or q, return it
If both subtrees return non-null, current node is LCA

Visualization

Tap to expand

Step-by-Step Walkthrough

Search Subtrees

Recursively search left and right subtrees for p and q

Check Results

If found both targets in different subtrees, current node is LCA

Bubble Up

Return found node upward to parent calls

Code -

solution.c — C

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

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

struct TreeNode* dfs(struct TreeNode* node, int p, int q) {
    if (!node) return NULL;
    
    if (node->val == p || node->val == q) {
        return node;
    }
    
    struct TreeNode* left = dfs(node->left, p, q);
    struct TreeNode* right = dfs(node->right, p, q);
    
    if (left && right) {
        return node;
    }
    
    return left ? left : right;
}

int solution(struct TreeNode* root, int p, int q) {
    struct TreeNode* lca = dfs(root, p, q);
    return lca->val;
}

int main() {
    printf("3\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node once in worst case

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

1.2M Views

High Frequency

~15 min Avg. Time

8.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler