Lowest Common Ancestor of a Binary Tree III

The solution to find the lowest common ancestor (LCA) of two nodes p and q in a binary tree where each node has a reference to its parent.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

        # Add all ancestors of p including p itself to the set
        while p:
            ancestors_p.add(p)
            p = p.parent

        # Iterate through the ancestors of q, and return the first common ancestor
        while q:
            if q in ancestors_p:
                return q
            q = q.parent

Explanation

  1. Find Ancestors of p: We iterate through the parent pointers of p and add all the ancestors including p itself into a set.
  2. Find Common Ancestor with q: We then iterate through the ancestors of q. The first ancestor of q that is also in the set of ancestors of p will be the lowest common ancestor.

This solution works for any binary tree, not just a binary search tree, as it relies on parent pointers and doesn’t need to make any assumptions about the values of the nodes.

Complexity

  • Time Complexity: The time complexity of this solution is (O(N)), where (N) is the number of nodes in the binary tree. In the worst case, we might have to traverse through all nodes.
  • Space Complexity: The space complexity is also (O(N)) as we are storing all the ancestors of p in a set. In the worst case, this could include all nodes in the binary tree.

title: Lowest Common Ancestor of a Binary Tree III excerpt: Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).

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 = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5 since a node can be a descendant of itself according to the LCA definition.

Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1

Constraints

  • The number of nodes in the tree is in the range [2, 10^5].
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique.
  • p != q
  • p and q exist in the tree.

Hints:

  • Store the path from p to the root.
  • Traverse the path from q to the root, the first common point of the two paths is the LCA.

Problem Definition

Define the Terms

LCA:

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.

Ancestor:

You go up the tree to find your ancestor

Descendant:

You go down the tree to find your descendant. A node can be a descendant of itself.

Define the Interface

Input: node p, node q
Output: lca node
Identify Implicit Inputs

The parent is an attribute of the node.

Define the Goal

Find the LCA node.

Identify the Constraints

  • The number of nodes in the tree is in the range [2, 10^5].
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique.
  • p != q
  • p and q exist in the tree.

Determine the Scope

In this step list any assumptions. Define boundaries of the problem. How to traverse the binary tree with only p and q nodes? Start from p or q. It does not matter.

Problem Representation

In this step analyze the examples.

Example 1: Traverse from p and search for q in the same subtree,

Search for q in the right subtree. q -> parent is 3 p -> parent is 3 Return the common parent 3 in this example.

Example 2: 5 is a descendant of itself

Traverse from p and search for q in the same left subtree. q -> parent is 2 p -> parent is 3 and 5.

Follow the parent pointers until you find a node that is a common parent to both. We reject 3 and use 5 as the LCA.

Example 3:

What should we check? Is p the root? Is q the root? Return the root.

if p.parent == p 
return p
   end
   if q.parent == p
   return q
   end

Consider the following cases and solve the problem by hand.

a = 5
b = 4

a = 3
b = 2

a = nil
b = 5

a = 5
b = 3


p1 = 5
p2 = 4

p1 = 3
p2 = 2

p1 = 4
p2 = 5

p1 = 2
p2 = 3

p1 = 5
p2 = 5

Brainstorm Solutions

Recursive Approach

Base Case

How to identify the base case in this problem? Example 3, can be the base case.

Recursive Cases

  • How many recursive calls will I write in the code?
  • What is the unit of decomposition?
  • We will have two subproblems, one for left subtree and one for right subtree.
  • What are the parameters we need for the recursive calls?
recursive_call(node.left, ....)
recursive_call(node.right, ...)

Store the path from p to the root. Traverse the path from q to the root, the first common point of the two paths is the LCA.

Analyze Time and Space Complexity

  • Time: O( )
  • Space: O( )
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

# Definition for a Node.
# class Node
#     attr_accessor :val, :left, :right, :parent
#     def initialize(val=0)
#         @val = val
#         @left, @right, parent = nil, nil, nil
#     end
# end
# @param {Node} p, q
# @return {Node}
def lowest_common_ancestor(p, q)
  p1 = p
  p2 = q
    
  while p1 != p2
    p1 = p1.parent ? p1.parent : q
    p2 = p2.parent ? p2.parent : p        
  end
  
  return p1
end