Practice/Amazon/Leetcode 1650. Lowest Common Ancestor of a Binary Tree III

Leetcode 1650. Lowest Common Ancestor of a Binary Tree III

CodingMust

Problem

You are given two nodes p and q from a binary tree. Each node has a reference to its parent node (in addition to left and right child pointers). The root node's parent is null.

Find and return the lowest common ancestor (LCA) of the two given nodes.

The lowest common ancestor is defined as the deepest node in the tree that has both p and q as descendants. Note that a node is considered a descendant of itself.

Requirements

1. You must use the parent pointers to solve this problem
2. Both nodes p and q are guaranteed to exist in the tree
3. All node values in the tree are unique
4. Return the actual node object, not just the value

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

Examples

Example 1:

` Tree structure: 3 /
5 1 /
6 2

Input: p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3 (the root) `

Example 2:

` Tree structure: 3 /
5 1 /
6 2

Input: p = 5, q = 6 Output: 5 Explanation: Node 5 is an ancestor of node 6, so the LCA is 5 itself `

Example 3:

` Tree structure: 3 /
5 1 / \ /
6 2 0 8 /
7 4

Input: p = 7, q = 4 Output: 2 Explanation: The lowest node that has both 7 and 4 as descendants is node 2 `