Find Lowest Common Ancestor in Binary Tree with Parent Link

Problem Statement

You are given two nodes, a and b, from a binary tree. Each node contains a link to its parent node. Your task is to determine their lowest common ancestor (LCA).

The node structure is defined as follows:

class TreeNode {
    public int value;
    public TreeNode leftChild;
    public TreeNode rightChild;
    public TreeNode parentNode;
}

The lowest common ancestor of two nodes a and b is defined as the deepest node in the tree that has both a and b as descendants (a node is considered a descendant of itself).

Examples

Example 1:

Node structure: [3,5,1,6,2,0,8,null,null,7,4]
a = 5, b = 1
Output: 3
Explanation: The lowest common ancestor of nodes 5 and 1 is 3.

Example 2:

Node structure: [3,5,1,6,2,0,8,null,null,7,4]
a = 5, b = 4
Output: 5
Explanation: The lowest common ancestor of nodes 5 and 4 is 5 since a node can be a descendant of itself.

Example 3:

Node structure: [1,2]
a = 1, b = 2
Output: 1

Constraints

• The total number of nodes in the tree is between 2 and 90,000.
• Each node's value is unique and lies in the range [-10⁸, 10⁸].
• Nodes a and b are distinct and both exist in the tree.