Skip to content

Instantly share code, notes, and snippets.

@liondancer

liondancer/lowest_common_ancestor_binary_tree.py

Created January 3, 2017 19:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save liondancer/89fce8cbf33780cd3504592ea1597dba to your computer and use it in GitHub Desktop.
Save liondancer/89fce8cbf33780cd3504592ea1597dba to your computer and use it in GitHub Desktop.
Download ZIP
Lowest Common Ancestor of a Binary Tree
Raw
lowest_common_ancestor_binary_tree.py
def lowestCommonAncestor(self, root, p, q):
# O(n) runtime and constant space
if root in (None, p, q): return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right:
return root
if left:
return left
return right
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment