Lowest Common Ancestor
Lowest Common Ancestor (LCA) in a Binary Tree
The Lowest Common Ancestor (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).
Problem Statement
Given a binary tree and two nodes p and q, find their lowest common ancestor.
Video Explanation
Node Class Representation
Solutions
- C++
- Java
- Python
- JavaScript
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
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;
}
}
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
var lowestCommonAncestor = function(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 || right;
};
Track Your Progress
Done with this topic? Mark it as complete to track your progress.
💬 Discuss this page
Have a question or spot something confusing in "Lowest Common Ancestor"? Ask below — it's backed by GitHub Discussions, so maintainers get notified like any other GitHub activity.