LeetCode: Lowest Common Ancestor

Lowest Common Ancestor of a Binary Search Tree | LeetCode OJ

Given 2 nodes of a tree we need to the lowest common ancestor. We can divide this easily into sub-problems. If both number are bigger than root then we can solve the problem for right subtree. If both numbers are smaller then we can reduce the problem to left subtree. Otherwise root is the answer. The algorithm is given below

1. If both values are greater than the root then move to right child
2. if both values are lesser than the root then move to left child
3. if one of the values match the current node then return it
4. if one value is greater and another bigger than current node return it

Since the last two cases have the same output we can combine them in the else section of the loop and move the root of left or right child in other cases

Remarks:

1. O(log n) time complexity for a balanced tree, as we need to travel from root to a leaf. O(n) in the worst case for a left/right deep tree
2. O(1) space complexity as no additional memory is used

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        while root:
            if p.val < root.val and q.val < root.val:
                root = root.left
            elif p.val > root.val and q.val > root.val:
                root = root.right
            else:
                return root