lowest_common_ancestor_of_a_binary_tree_iii 

 1# Definition for a Node.
 2
 3# @leet start
 4class Node:
 5    def __init__(self, val):
 6        self.val = val
 7        self.left = None
 8        self.right = None
 9        self.parent = None
10
11
12class Solution:
13    def lowestCommonAncestor(self, p: Node, q: Node) -> Node:
14        """
15        This question is like finding a cycle in a linked list. We're given
16        two nodes inside a binary tree and have to find the lowest common ancestor
17        We can create a set, where we iterate up the parent pointers for the
18        first pointer, saving all values we see, and then for the other side,
19        iterating up until we see a value we've already visited, and that would be
20        the LCA. That would take $O(h)$ time and $O(h)$ space for the set.
21
22        We can do better.
23
24        This can be done in $O(h)$ time and $O(1)$ space. Imagine the steps to
25        find the LCA are `m` and `n` for `p` and `q` respectively. Say we take `p`
26        and move it up to the root in `m` steps. If we were to take `n` extra steps
27        by swapping its position to `q` and iterate up again, and do the same for
28        the original `q`, we would find the LCA in `O(m + n)$` time which is $O(h)$
29        and both pointers will meet at the LCA.
30        """
31        p1, p2 = p, q
32        while p1 != p2:
33            p1 = p1.parent if p1.parent else q
34            p2 = p2.parent if p2.parent else p
35        return p1
36
37
38# @leet end
39
40
41def test():
42    assert 2 + 2 == 4
class Node: 
 5class Node:
 6    def __init__(self, val):
 7        self.val = val
 8        self.left = None
 9        self.right = None
10        self.parent = None
Node(val) 
 6    def __init__(self, val):
 7        self.val = val
 8        self.left = None
 9        self.right = None
10        self.parent = None
val
left
right
parent
class Solution: 
13class Solution:
14    def lowestCommonAncestor(self, p: Node, q: Node) -> Node:
15        """
16        This question is like finding a cycle in a linked list. We're given
17        two nodes inside a binary tree and have to find the lowest common ancestor
18        We can create a set, where we iterate up the parent pointers for the
19        first pointer, saving all values we see, and then for the other side,
20        iterating up until we see a value we've already visited, and that would be
21        the LCA. That would take $O(h)$ time and $O(h)$ space for the set.
22
23        We can do better.
24
25        This can be done in $O(h)$ time and $O(1)$ space. Imagine the steps to
26        find the LCA are `m` and `n` for `p` and `q` respectively. Say we take `p`
27        and move it up to the root in `m` steps. If we were to take `n` extra steps
28        by swapping its position to `q` and iterate up again, and do the same for
29        the original `q`, we would find the LCA in `O(m + n)$` time which is $O(h)$
30        and both pointers will meet at the LCA.
31        """
32        p1, p2 = p, q
33        while p1 != p2:
34            p1 = p1.parent if p1.parent else q
35            p2 = p2.parent if p2.parent else p
36        return p1
def lowestCommonAncestor( self, p: Node, q: Node) -> Node: 
14    def lowestCommonAncestor(self, p: Node, q: Node) -> Node:
15        """
16        This question is like finding a cycle in a linked list. We're given
17        two nodes inside a binary tree and have to find the lowest common ancestor
18        We can create a set, where we iterate up the parent pointers for the
19        first pointer, saving all values we see, and then for the other side,
20        iterating up until we see a value we've already visited, and that would be
21        the LCA. That would take $O(h)$ time and $O(h)$ space for the set.
22
23        We can do better.
24
25        This can be done in $O(h)$ time and $O(1)$ space. Imagine the steps to
26        find the LCA are `m` and `n` for `p` and `q` respectively. Say we take `p`
27        and move it up to the root in `m` steps. If we were to take `n` extra steps
28        by swapping its position to `q` and iterate up again, and do the same for
29        the original `q`, we would find the LCA in `O(m + n)$` time which is $O(h)$
30        and both pointers will meet at the LCA.
31        """
32        p1, p2 = p, q
33        while p1 != p2:
34            p1 = p1.parent if p1.parent else q
35            p2 = p2.parent if p2.parent else p
36        return p1

This question is like finding a cycle in a linked list. We're given two nodes inside a binary tree and have to find the lowest common ancestor We can create a set, where we iterate up the parent pointers for the first pointer, saving all values we see, and then for the other side, iterating up until we see a value we've already visited, and that would be the LCA. That would take $O(h)$ time and $O(h)$ space for the set.

We can do better.

This can be done in $O(h)$ time and $O(1)$ space. Imagine the steps to find the LCA are m and n for p and q respectively. Say we take p and move it up to the root in m steps. If we were to take n extra steps by swapping its position to q and iterate up again, and do the same for the original q, we would find the LCA in O(m + n)$ time which is $O(h)$ and both pointers will meet at the LCA.

def test(): 
42def test():
43    assert 2 + 2 == 4