SA
메인 내용으로 이동

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)O(N) where NN is the count of the nodes. Space complexity will be O(N)O(N) for constructing lists and dictionaries.

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