Lowest Common Ancestor (With Parent Pointers)

1def lca(node1: TreeNode, node2: TreeNode) -> TreeNode:
2    def depth(node: TreeNode) -> int:
3        d = 0
4        while node:
5            node = node.parent
6            d += 1
7        return d
8    d1, d2 = depth(node1), depth(node2)
9    while d1 > d2:
10        node1 = node1.parent
11        d1 -= 1
12    while d2 > d1:
13        node2 = node2.parent
14        d2 -= 1
15    while node1 != node2:
16        node1 = node1.parent
17        node2 = node2.parent
18    return node1