Lowest Common Ancestor of a Binary Search Tree

From LeetCode

problem description / solution

Solution in Python3

# 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':
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        return root       

I am lucky to get

Runtime: 88 ms, faster than 72.89% of Python3 online submissions for Lowest Common Ancestor of a Binary Search Tree.

Time Complexity

\(O(h)\), where \(h\) is the height of the tree.

Note: LeetCode’s solution says the time complexity is \(O(n)\), where \(n\) is the number of nodes. Well, \(O(h) = O(n)\) only in those worst trees.