Problem Statement:
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “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).”
Examples:
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1
Constraints:
- The number of nodes in the tree is in the range
[2, 105 -109 <= Node.val <= 109- All
Node.valare unique p != qpandqwill exist in the tree.
Approach
- Use post-order traversal to explore the tree.
- Recursively count how many of the target nodes (
porq) are found in the left and right subtrees. - If the current node is either
porq, increment the count. - When the total count from
left + right + current nodebecomes 2, this node is the Lowest Common Ancestor. - Return the stored lca node after traversal.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(h) (h=tree height)
Dry Run
Function Call: isSubtree(root, subRoot) where
root = TreeNode(3)
├── left: TreeNode(4)
│ ├── left: TreeNode(1)
│ └── right: TreeNode(2)
└── right: TreeNode(5)
subRoot = TreeNode(4)
├── left: TreeNode(1)
└── right: TreeNode(2)
Step 1:
→ Call serialize(root)
Serializing root:
→ curr = 3 → hash = “-3”
→ curr.left = 4 → hash = “-3-4”
→ curr.left.left = 1 → hash = “-3-4-1”
→ curr.left.left.left = null → hash = “-3-4-1-#”
→ curr.left.left.right = null → hash = “-3-4-1-#-#”
→ curr.left.right = 2 → hash = “-3-4-1-#-#-2”
→ curr.left.right.left = null → hash = “-3-4-1-#-#-2-#”
→ curr.left.right.right = null → hash = “-3-4-1-#-#-2-#-#”
→ curr.right = 5 → hash = “-3-4-1-#-#-2-#-#-5”
→ curr.right.left = null → hash = “-3-4-1-#-#-2-#-#-5-#”
→ curr.right.right = null → hash = “-3-4-1-#-#-2-#-#-5-#-#”
Serialized root:
→ hashRoot = “-3-4-1-#-#-2-#-#-5-#-#”
Step 2:
→ Call serialize(subRoot)
Serializing subRoot:
→ curr = 4 → hash = “-4”
→ curr.left = 1 → hash = “-4-1”
→ curr.left.left = null → hash = “-4-1-#”
→ curr.left.right = null → hash = “-4-1-#-#”
→ curr.right = 2 → hash = “-4-1-#-#-2”
→ curr.right.left = null → hash = “-4-1-#-#-2-#”
→ curr.right.right = null → hash = “-4-1-#-#-2-#-#”
Serialized subRoot:
→ hashSubRoot = “-4-1-#-#-2-#-#”
Step 3:
→ Check if hashRoot includes hashSubRoot:
→ “-3-4-1-#-#-2-#-#-5-#-#” includes “-4-1-#-#-2-#-#” → true
Final Result: true
root = TreeNode(3)
├── left: TreeNode(4)
│ ├── left: TreeNode(1)
│ └── right: TreeNode(2)
└── right: TreeNode(5)
subRoot = TreeNode(4)
├── left: TreeNode(1)
└── right: TreeNode(2)
Step 1:
→ Call serialize(root)
Serializing root:
→ curr = 3 → hash = “-3”
→ curr.left = 4 → hash = “-3-4”
→ curr.left.left = 1 → hash = “-3-4-1”
→ curr.left.left.left = null → hash = “-3-4-1-#”
→ curr.left.left.right = null → hash = “-3-4-1-#-#”
→ curr.left.right = 2 → hash = “-3-4-1-#-#-2”
→ curr.left.right.left = null → hash = “-3-4-1-#-#-2-#”
→ curr.left.right.right = null → hash = “-3-4-1-#-#-2-#-#”
→ curr.right = 5 → hash = “-3-4-1-#-#-2-#-#-5”
→ curr.right.left = null → hash = “-3-4-1-#-#-2-#-#-5-#”
→ curr.right.right = null → hash = “-3-4-1-#-#-2-#-#-5-#-#”
Serialized root:
→ hashRoot = “-3-4-1-#-#-2-#-#-5-#-#”
Step 2:
→ Call serialize(subRoot)
Serializing subRoot:
→ curr = 4 → hash = “-4”
→ curr.left = 1 → hash = “-4-1”
→ curr.left.left = null → hash = “-4-1-#”
→ curr.left.right = null → hash = “-4-1-#-#”
→ curr.right = 2 → hash = “-4-1-#-#-2”
→ curr.right.left = null → hash = “-4-1-#-#-2-#”
→ curr.right.right = null → hash = “-4-1-#-#-2-#-#”
Serialized subRoot:
→ hashSubRoot = “-4-1-#-#-2-#-#”
Step 3:
→ Check if hashRoot includes hashSubRoot:
→ “-3-4-1-#-#-2-#-#-5-#-#” includes “-4-1-#-#-2-#-#” → true
Final Result: true
var lowestCommonAncestor = function(root, p, q) {
let lca = null;
let traversal = (curr) => {
let count = 0;
if(!curr) return 0;
let ansOnLeft = traversal(curr.left);
let ansOnRight = traversal(curr.right);
if(curr.val === p.val || curr.val === q.val) {
++count;
}
count = count + ansOnLeft + ansOnRight;
if(count === 2 && !lca) {
lca = curr;
}
return count;
}
traversal(root);
return lca;
};
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def lowestCommonAncestor(self, root, p, q):
# Base case
if not root or root == p or root == q:
return root
# Search in left and right subtree
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
# If both sides return non-null → current node is LCA
if left and right:
return root
# Otherwise return the non-null side
return left if left else right
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Base case
if (root == null || root == p || root == q) {
return root;
}
// Search in left and right subtree
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// If both sides are non-null → LCA found
if (left != null && right != null) {
return root;
}
// Return non-null side
return (left != null) ? left : right;
}
}
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) {
val = x;
left = right = NULL;
}
};
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// Base case
if (root == NULL || root == p || root == q)
return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
// If both sides return non-null → LCA
if (left != NULL && right != NULL)
return root;
// Otherwise return non-null side
return (left != NULL) ? left : right;
}
};
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
// Base case
if (root == NULL || root == p || root == q)
return root;
struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
struct TreeNode* right = lowestCommonAncestor(root->right, p, q);
// If both sides are non-null → LCA
if (left != NULL && right != NULL)
return root;
// Return non-null side
return (left != NULL) ? left : right;
}
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
val = x;
}
}
public class Solution {
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Base case
if (root == null || root == p || root == q)
return root;
TreeNode left = LowestCommonAncestor(root.left, p, q);
TreeNode right = LowestCommonAncestor(root.right, p, q);
// If both sides return non-null → LCA
if (left != null && right != null)
return root;
// Otherwise return non-null side
return (left != null) ? left : right;
}
}
