Lowest Common Ancestor

Example: Let's consider the following binary tree:

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4 

#We want to find the LCA of nodes 5 and 1. 

# Definition for a binary tree node
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 the root is None or matches either p or q, it is the LCA
        if root is None or root == p or root == q:
            return root

        # Recurse on the left and right subtrees
        left_lca = self.lowestCommonAncestor(root.left, p, q)
        right_lca = self.lowestCommonAncestor(root.right, p, q)

        # If both left_lca and right_lca are not None, it means p and q are on different subtrees,
        # so the current root is the LCA
        if left_lca and right_lca:
            return root

        # If only one of left_lca or right_lca is not None, it means p and q are on the same subtree,
        # so return that non-None value as the LCA
        return left_lca or right_lca

# Construct the binary tree
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)

# Create an instance of the Solution class
solution = Solution()

# Find the LCA of nodes 5 and 1
lca = solution.lowestCommonAncestor(root, root.left, root.right)
print("Lowest Common Ancestor:", lca.val)
# Output: Lowest Common Ancestor: 3

In this example, we define a binary tree using the TreeNode class. The lowestCommonAncestor method of the Solution class takes the root of the tree and two nodes p and q as input. It recursively searches for the lowest common ancestor of p and q in the binary tree.

The algorithm follows these steps:

1. Base case: If the root is None or matches either p or q, it is the LCA. Return the root in this case.
2. Recursively call the lowestCommonAncestor function on the left and right subtrees.
3. If both the left and right LCA are not None, it means p and q are on different subtrees, so the current root is the LCA.
4. If only one of the left or right LCA is not None, it means p and q are on the same subtree. Return the non-None value as the LCA.
5. If both left and right LCA are None, return None.

We create an instance of the Solution class and call the lowestCommonAncestor method to find the LCA of nodes 5 and 1. The LCA is obtained by accessing the val attribute of the returned node.

The time complexity of this algorithm is O(N), where N is the number of nodes in the binary tree. In the worst case, we need to visit all the nodes of the tree. The space complexity is O(N) as well, considering the recursive calls that are placed on the call stack.

A related question that can be solved using the LCA concept is "Lowest Common Ancestor of a Binary Tree" .

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

# Definition for a binary tree node
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 the root is None or matches either p or q, it is the LCA
        if root is None or root == p or root == q:
            return root

        # Recurse on the left and right subtrees
        left_lca = self.lowestCommonAncestor(root.left, p, q)
        right_lca = self.lowestCommonAncestor(root.right, p, q)

        # If both left_lca and right_lca are not None, it means p and q are on different subtrees,
        # so the current root is the LCA
        if left_lca and right_lca:
            return root

        # If only one of left_lca or right_lca is not None, it means p and q are on the same subtree,
        # so return that non-None value as the LCA
        return left_lca or right_lca

# Example usage
# Construct the binary tree
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)

# Create an instance of the Solution class
solution = Solution()

# Find the LCA of nodes with values 5 and 1
p = TreeNode(5)
q = TreeNode(1)
lca = solution.lowestCommonAncestor(root, p, q)
print("Lowest Common Ancestor:", lca.val)
# Output: Lowest Common Ancestor: 3

In this solution, we reuse the lowestCommonAncestor method from the previous explanation. We create a binary tree with the given nodes and construct an instance of the Solution class. We then call the lowestCommonAncestor method to find the LCA of nodes 5 and 1. The LCA node is accessed using the val attribute and printed.

You can modify the values of p and q to find the LCA of different nodes in the binary tree.

The time complexity of this solution is O(N), where N is the number of nodes in the binary tree. The space complexity is also O(N) due to the recursion and call stack usage.