1650. Lowest Common Ancestor of a Binary Tree III - Explanation

Problem Link

Description

You are given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).

Each node will have a reference to its parent node. The definition for Node is below:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)."

Example 1:

Input: root = [5,3,4,2,1], p = 1, q = 2

Output: 3

Example 2:

Input: root = [5,3,4,2,1,null,9,null,11,10,12], p = 3, q = 12

Output: 3

Constraints:

  • 2 <= The number of nodes in the tree <= 100,000.
  • -1,000,000,000 <= Node.val <= 1,000,000,000
  • All Node.val are unique.
  • p != q
  • p and q will both exist in the tree.

Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Hash Set

"""
# 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':
        seen = set()
        while p:
            seen.add(p)
            p = p.parent

        while q:
            if q in seen:
                return q
            q = q.parent

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

2. Iteration - I

"""
# 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':
        def height(node):
            h = 0
            while node:
                h += 1
                node = node.parent
            return h

        h1, h2 = height(p), height(q)
        if h2 < h1:
            p, q = q, p

        diff = abs(h1 - h2)
        while diff:
            q = q.parent
            diff -= 1

        while p != q:
            p = p.parent
            q = q.parent

        return p

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)

3. Iteration - II

"""
# 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':
        ptr1, ptr2 = p, q
        while ptr1 != ptr2:
            ptr1 = ptr1.parent if ptr1 else q
            ptr2 = ptr2.parent if ptr2 else p
        return ptr1

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)