Lowest Common Ancestor (LCA) in a Binary Tree

Algorithm Steps

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

Lowest Common Ancestor (LCA) in a Binary Tree - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

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: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left if left else right

# Example usage:
if __name__ == '__main__':
    # Construct binary tree:
    #         3
    #        / \
    #       5   1
    #      / \ / \
    #     6  2 0  8
    #       / \
    #      7   4
    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)

    sol = Solution()
    # Assume we want to find LCA of nodes 7 and 4
    lca = sol.lowestCommonAncestor(root, root.left.right.left, root.left.right.right)
    print('LCA:', lca.val if lca else 'None')