Is Lowest Common Ancestor of a Binary Tree III easy or hard?

The problem is rated Medium because it requires recognizing that parent pointers change the traversal strategy. Once you model ancestor paths like linked lists, the two-pointer solution becomes straightforward.

Lowest Common Ancestor of a Binary Tree III Python/Java solution

In Python or Java, the hash set solution stores ancestors of one node and checks the other node while traversing upward. The optimal solution uses two pointers moving through parent references until they meet. Both implementations run in O(h) time and are commonly used in coding interviews.

How to solve Lowest Common Ancestor of a Binary Tree III in O(n)?

Traverse ancestors using parent pointers instead of exploring the whole tree. One method stores all ancestors of node p in a hash set, then walks upward from node q until a match is found. Another method uses two pointers that switch starting nodes when reaching the root, guaranteeing an intersection at the LCA.

What is the best approach for Lowest Common Ancestor of a Binary Tree III?

The two-pointer approach is typically the best solution. Each pointer starts at one node and moves upward using parent pointers. When a pointer reaches null, it switches to the other node's starting position. Both pointers eventually meet at the lowest common ancestor with O(h) time and O(1) space.

Is Lowest Common Ancestor of a Binary Tree III asked at Google/Amazon/Meta?

Lowest Common Ancestor variations appear frequently in interviews at companies like Google, Amazon, Meta, and Microsoft. This version is common because the parent pointer changes the typical tree traversal strategy and tests understanding of pointer techniques.

What data structure is used in Lowest Common Ancestor of a Binary Tree III?

Common implementations use a hash set to store visited ancestors or a two-pointer technique similar to linked list intersection. The underlying structure is a binary tree with parent pointers, which allows upward traversal without starting from the root.

What is the time complexity of Lowest Common Ancestor of a Binary Tree III?

The optimal solutions run in O(h) time, where h is the height of the tree. Each pointer or traversal moves upward through ancestors until the lowest common ancestor is found. In the worst case, this is proportional to the depth of the nodes from the root.

Description Hints 2 Solution Video 16:38

1650. Lowest Common Ancestor of a Binary Tree III

Medium83.0% acceptance10 companiesPremium elsewhere, free here

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⁵].
-10⁹ <= Node.val <= 10⁹
All Node.val are unique.
p != q
p and q exist in the tree.

Asked at 10 companies

Meta LinkedIn Wix MongoDB Amazon Microsoft Apple Atlassian

Google Yandex

Topics

Hints open one at a time

Hint 1

Store the path from p to the root.

Hint 2

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

16:38

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution