Last active
March 15, 2020 19:55
-
-
Save nma/846ac037662fccb3eb0761ccec0d0781 to your computer and use it in GitHub Desktop.
Lowest Common Ancestor Algorithm with Parent Pointers
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def find_lca(n1: BinaryTreeNode, n2: BinaryTreeNode) -> BinaryTreeNode: | |
def get_depth(node: BinaryTreeNode) -> int: | |
depth = 0 | |
while node and node.parent: | |
node = node.parent | |
depth += 1 | |
return depth | |
d1 = get_depth(n1) | |
d2 = get_depth(n2) | |
while d1 > d2: | |
n1 = n1.parent | |
d1 -= 1 | |
while d2 > d1: | |
n2 = n2.parent | |
d2 -= 1 | |
while n1 != n2 and d1 > 0: | |
d1 -= 1 | |
n1 = n1.parent | |
n2 = n2.parent | |
return n1 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment