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

I tackle the problem of finding the Lowest Common Ancestor (LCA) in a Binary Search Tree (BST). I explain the time and space complexities involved. This concise walkthrough is perfect for anyone looking to understand how to efficiently determine the LCA and grasp the underlying algorithmic principles.

Python Code:

# 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':
        #BST Time complexity : Best case(balance tree): O(log n) & Worst Case(skewed tree) O(n)

        while root:

            #assign variable
            root_value = root.val

            p_value = p.val

            q_value = q.val


            #conditions

            #Move to the left child if the p and q are less the current root node
            if p_value < root_value and q_value < root_value:
                root = root.left

            #Move to the RIGHT child if the p and q are MORE the current root node
            elif p_value > root_value and q_value > root_value:
                root = root.right

            else:
                return root

        return None

    #SIZE Complexity is O(1)