236. Lowest Common Ancestor of a Binary Tree | LeetCode Using Python

In this video, I walk through solving the “236. Lowest Common Ancestor of a Binary Tree” problem from LeetCode using Python. I explain how to find the Lowest Common Ancestor (LCA) of two nodes in a binary tree using a recursive approach. This method efficiently navigates through the tree to determine the deepest node where both given nodes are present in its subtrees. Below is the code used in the video, complete with detailed comments to help you understand each step of the solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

        #Recursively DFS approach
        #Time Complexity: O(N) n being nodes; each node will be visited until we find the values(p and q)
        #Size complexity: O(H) h being height. in a balance tree it will be O(log n) in a skewed it will be O(n)

        #Base Case
        if root is None or root == p or root is q:
            return root

        left_subtree = self.lowestCommonAncestor(root.left,p, q)
        right_subtree = self.lowestCommonAncestor(root.right,p, q)

        #For example we find p in left_subtree and q in right_subtree return root: 1 for each subtree
        if left_subtree and right_subtree:
            return root
        
        else: # which ever subtree has both p and q: 1 subtree has both the other has none
            return left_subtree or right_subtree


        #find the lowest common ancestor (LCA) of two given nodes in the tree.