Lowest Common Ancestor Of A Binary Tree - Leetcode Solution

Problem Description:

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

Example:

Input: 3 /
5 1 / \ /
6 2 7 4

p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.

Solution:

To solve this problem, we need to traverse the binary tree and find the paths from the root to the two nodes p and q. Once we have the paths, we can find the last common node in the two paths, which will be the LCA.

For traversing the binary tree, we can use depth-first search (DFS) algorithm. We can define a recursive function findPath(root, node, path) that will take a root node, a node to find, and a list path that will contain the path from root to node. The function will return True if the node is found, False otherwise.

The main function lowestCommonAncestor(root, p, q) will call the findPath function twice to find the paths from the root to the two nodes p and q. Then it will iterate over the paths and find the last common node in the two paths.

Here is the Python code:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def findPath(root, node, path):
    if not root:
        return False
    
    path.append(root)
    
    if root == node:
        return True
    
    if (root.left and findPath(root.left, node, path)) or \
       (root.right and findPath(root.right, node, path)):
        return True
    
    path.pop()
    return False

def lowestCommonAncestor(root, p, q):
    path1 = []
    findPath(root, p, path1)
    
    path2 = []
    findPath(root, q, path2)
    
    i = 0
    while i < len(path1) and i < len(path2) and path1[i] == path2[i]:
        i += 1
    
    return path1[i-1] if i > 0 else None

Time Complexity:

The time complexity of this method is O(N) where N is the number of nodes in the binary tree. In the worst case, we might need to traverse all the nodes to find the LCA.

Space Complexity:

The space complexity of this method is O(N) because we are storing the path lists for two nodes, which can have at most N nodes in total.

1