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 = None

class 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.