Lowest Common Ancestor of a Binary Search Tree

The problem description can be found in LeetCode.

Approach

The problem states that the Tree that we take as input is a Binary Search Tree. So we surely have to take this into consideration for our final algorithm. We have to take advantage of this property to derive our solution.

One thing we can notice here is that if the nodes we are looking for are in different sub-trees, then, the LCA is the root node itself. However, if they belong to the same sub-tree, it means that both nodes are either fewer (left sub-tree) or greater (right sub-tree) than the node itself. So we can recursively continue our search on the proper sub-tree.

Solution

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

        while lca:
            if p.val > lca.val and q.val > lca.val:
                lca = lca.right
            elif p.val < lca.val and q.val < lca.val:
                lca = lca.left
            else:
                break

        return lca

Complexity

• Time: $O(h)$
• Space: $O(1)$

Where $h$ is the height of the tree. If the tree is unbalanced, it is like having a Linked List, hence $h=n$.