Practice/LinkedIn/Leetcode 236. Lowest Common Ancestor of a Binary Tree

Leetcode 236. Lowest Common Ancestor of a Binary Tree

CodingMust

Problem

You are given the root of a binary tree along with two distinct node values p and q that are guaranteed to exist somewhere in the tree. Your task is to identify and return the value of the lowest common ancestor (LCA) of these two nodes.

The lowest common ancestor is defined as the node positioned deepest in the tree that has both p and q as descendants. Note that a node is considered a descendant of itself, meaning if one of the target values is an ancestor of the other, it serves as its own LCA.

Requirements

1. Return the value of the lowest common ancestor node
2. Handle cases where one target node is an ancestor of the other
3. Both target nodes are guaranteed to exist in the tree
4. All node values in the tree are unique

Constraints

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

Examples

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. Node 3 is the root and both target nodes appear in different subtrees.

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 an ancestor of itself. Node 4 is a descendant of node 5.

Example 3:

Input: root = [1,2], p = 1, q = 2 Output: 1 Explanation: In a simple two-node tree, the root is the LCA.