# 0235 LCA of a Binary Search Tree

Solved at: 2022-09-25. Took 17m 09s

## Question​

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to thedefinition of LCA on Wikipedia: "The lowest common ancestor is defined between two nodespandqas the lowest node inTthat has bothpandqas descendants (where we allowa node to be a descendant of itself)."

## Solution​

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':        found_p = False        found_q = False        queue = [root]        ancestor = {}        while((not found_p or not found_q) and queue):            current = queue.pop()            if not current:                continue            left = current.left            right = current.right            if left:                ancestor[left] = current                if p.val == left.val:                    found_p = True                if q.val == left.val:                    found_q = True            if right:                ancestor[right] = current                if p.val == right.val:                    found_p = True                if q.val == right.val:                    found_q = True            queue.append(left)            queue.append(right)        current = p        p_path = [current]        while current != root:            current = ancestor[current]            p_path.append(current)        current = q        q_path = [current]        while current != root:            current = ancestor[current]            q_path.append(current)        lca = root        for i in p_path:            print(i.val, "<-", end=" ")        print()        for i in q_path:            print(i.val, "<-", end=" ")        for i in range(-1, -1 * min(len(q_path), len(p_path)) - 1, -1):            if q_path[i] == p_path[i]:                lca = p_path[i]            elif q_path[i] != p_path[i]:                break        return lca

I misunderstood LCA as being the minimum in value.

## Results​

### Runtime​

• 89 ms, faster than 86.27% of Python3 online submissions for the Lowest Common Ancestor of a Binary Search Tree.

### Memory Usage​

• 18.9 MB, less than 23.33% of Python3 online submissions for the Lowest Common Ancestor of a Binary Search Tree.

## Improvements​

I ignored that this is a Binary Search Tree, not just Binary Tree. Therefore one can binary search to reduce the search scope.

## Complexity Analysis​

For this, It will be $O(N)$ where $N$ is the count of the nodes. Space complexity will be $O(N)$ for constructing lists and dictionaries.

If we use the above improvement, space complexity will reduce to $O(1)$. However, time complexity will not change.