Given a binary search tree (BST), discover the bottom widespread ancestor (LCA) node of two given nodes within the BST.
In response to the definition of LCA on Wikipedia: “The bottom widespread ancestor is outlined between two nodes p and q because the lowest node in T that has each p and q as descendants (the place we enable a node to be a descendant of itself).”
class Answer:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root == None:
return None
node = root
whereas node:
if node.val < p.val and node.val < q.val:
node = node.proper
if node.val > p.val and node.val > q.val:
node = node.left
else:
break
return node
