Lowest common ancestor of a binary tree (not a BST)
Home | Coding Interviews | Simple Data Structures | Lowest common ancestor of a binary tree (not a BST)
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
The LCA is defined as: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
# If looking for me, return myself
if root == p or root == q:
return root
left = right = None
# else look in left and right child
if root.left:
left = self.lowestCommonAncestor(root.left, p, q)
if root.right:
right = self.lowestCommonAncestor(root.right, p, q)
# if both children returned a node, means
# both p and q found so parent is LCA
if left and right:
return root
else:
# either one of the chidren returned a node, meaning either p or q found on left or right branch.
# Example: assuming 'p' found in left child, right child returned 'None'. This means 'q' is
# somewhere below node where 'p' was found we dont need to search all the way,
# because in such scenarios, node where 'p' found is LCA
return left or right
Posted by Jamie Meyer 20 days ago