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.


Explanation
 Find Ancestors of
p
: We iterate through the parent pointers ofp
and add all the ancestors includingp
itself into a set.  Find Common Ancestor with
q
: We then iterate through the ancestors ofq
. The first ancestor ofq
that is also in the set of ancestors ofp
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
andq
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( )

