DSA Series Chapter 27 : Lowest Common Ancestor (LCA) in Binary Tree (Python Version)
1. Objective
To find the Lowest Common Ancestor (LCA) of two nodes in a Binary Tree using a recursive Python approach.
2. Definition (Exam-Oriented)
The Lowest Common Ancestor (LCA) of two nodes
n1andn2is the deepest node that has both nodes as descendants.
3. Why This Problem Is Important
Frequently asked in interviews
Core concept for tree recursion
Used in advanced problems (distance between nodes, subtree queries)
4. Example Tree
1
/ \
2 3
/ \
4 5
LCA(4, 5) → 2
LCA(4, 3) → 1
5. Logic (High-Level)
If current node is
None→ returnNoneIf current node matches
n1orn2→ return current nodeRecursively search left subtree
Recursively search right subtree
If both sides return a node → current node is LCA
Else return the non-
Noneresult
6. Node Definition (Python Class)
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
7. Function to Find LCA
def find_lca(root, n1, n2):
if root is None:
return None
if root.data == n1 or root.data == n2:
return root
left_lca = find_lca(root.left, n1, n2)
right_lca = find_lca(root.right, n1, n2)
if left_lca and right_lca:
return root
return left_lca if left_lca else right_lca
8. Line-by-Line Explanation
if root is None:
return None
Tree exhausted, stop recursion
if root.data == n1 or root.data == n2:
return root
If current node is one of the targets
left_lca = find_lca(root.left, n1, n2)
right_lca = find_lca(root.right, n1, n2)
Search both subtrees
if left_lca and right_lca:
return root
One node found on each side → current node is LCA
return left_lca if left_lca else right_lca
Return whichever side found a node
9. Complete Python Program
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def find_lca(root, n1, n2):
if root is None:
return None
if root.data == n1 or root.data == n2:
return root
left_lca = find_lca(root.left, n1, n2)
right_lca = find_lca(root.right, n1, n2)
if left_lca and right_lca:
return root
return left_lca if left_lca else right_lca
# -------- Main --------
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
n1, n2 = 4, 5
lca = find_lca(root, n1, n2)
if lca:
print(f"LCA of {n1} and {n2} is {lca.data}")
else:
print("LCA not found")
10. Output
LCA of 4 and 5 is 2
11. Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(h)
12. C vs Python Comparison
| Aspect | C | Python |
|---|---|---|
| NULL | NULL | None |
| Structure | struct | class |
| Return | pointer | object reference |
| Memory | manual | automatic |
Comments
Post a Comment