_1650. Lowest Common Ancestor of a Binary Tree III.md

1650. Lowest Common Ancestor of a Binary Tree III

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 10, 2024

Last updated : July 01, 2024

---

Related Topics : Hash Table, Two Pointers, Tree, Binary Tree

Acceptance Rate : 80.73 %

---

Solutions

• m1650 v2.py
• m1650 v3 O(1) Space.py
• m1650.py

Python

m1650 v2.py

# Optimized version to account for very large graphs since we don't know which one is lower
"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        visited = set()

        while True :
            if p and q :
                if p in visited :
                    return p
                visited.add(p)

                if q in visited :
                    return q
                visited.add(q)

                p = p.parent
                q = q.parent
            
            elif p :
                while p :
                    if p in visited :
                        return p
                    p = p.parent
            elif q :
                while q :
                    if q in visited :
                        return q
                    q = q.parent
            else :
                break
        
        return None


        return None

m1650 v3 O(1) Space.py

# O(1) SPACE ATTEMPT
"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':

        # Find depths of each
        pDepth, qDepth = 0, 0
        curr = p
        while curr :
            pDepth += 1
            curr = curr.parent
        curr = q
        while curr :
            qDepth += 1
            curr = curr.parent

        # Make depths match and be equal
        while pDepth > qDepth :
            p = p.parent
            pDepth -= 1
        while qDepth > pDepth :
            q = q.parent
            qDepth -= 1

        # Go up till equal and output
        while p and q :
            if p == q :
                return p
            p = p.parent
            q = q.parent

        # Not connected tree
        return None

m1650.py

"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        visited = set()

        curr = p
        while curr :
            visited.add(curr)
            curr = curr.parent
        
        curr = q
        while curr :
            if curr in visited :
                return curr
            curr = curr.parent

        return None