Leetcode 236 : Lowest common Ancestor of a Binary Tree (Solution in python )

class Solution:
  def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if not root or root == p or root == q:
      return root

    l = self.lowestCommonAncestor(root.left, p, q)
    r = self.lowestCommonAncestor(root.right, p, q)

    if l and r:
      return root
    return l or r

This `lowestCommonAncestor` method finds the lowest common ancestor (LCA) of two nodes `p` and `q` in a binary tree. Here’s an explanation of the code and its complexity:

1. The base case checks if `root` is None or if `root` is either `p` or `q`. If true, it returns `root`.

2. Recursively calls `lowestCommonAncestor` on the left and right subtrees, storing the results in `l` and `r`.

3. If both `l` and `r` are not None (i.e., both `p` and `q` are found in different subtrees), `root` is the LCA, so it returns `root`.

4. If either `l` or `r` is None (i.e., both `p` and `q` are in the same subtree), it returns the non-None value (either `l` or `r`), which is the LCA.

- **Time Complexity**: In the worst case, it traverses the entire tree once. The time complexity is O(n), where n is the number of nodes in the tree.

- **Space Complexity**: The recursion stack can go as deep as the height of the tree. In a balanced tree, the space complexity is O(log n), but it can be O(n) in the worst case for an unbalanced tree.

This approach optimizes the search by traversing the tree only once and efficiently finding the LCA.