Lowest Common Ancestor of a Binary Tree III

Problem Overview
Lowest Common Ancestor of a Binary Tree III (LeetCode #1650) asks you to find the lowest common ancestor (LCA) of two given nodes p and q in a binary tree where each node has a parent pointer, tagged with Tree, Hash Table, Two Pointers, and Binary Tree.[1][3][5]

Full Problem Statement

Given two nodes p and q of a binary tree, return their lowest common ancestor (LCA). Each node has a reference to its parent node.

The LCA is defined as the lowest node in the tree that has both p and q as descendants (a node can be a descendant of itself). All nodes in the tree are unique, p != q, and both nodes are guaranteed to exist.[3][5][9][1]

Node Definition (Python example):
python class Node: def __init__(self, val): self.val = val self.left = None self.right = None self.parent = None

Input/Output Examples

Example 1 (from standard tree visualization):
Tree structure:
3 / \ 5 1 / \ \ 6 2 8 / \ 7 4

• Input: p = Node(5), q = Node(1)
• Output: Node(3) (root, common ancestor)[5][3]

Example 2 (paths intersect deeper):

• Input: p = Node(6), q = Node(8)
• Traversal from 6: 6→5→3
• Traversal from 8: 8→1→3
• Output: Node(3) (first intersection at root)[3][5]

Example 3 (direct siblings):
3 / 5 / \ 6 2

• Input: p = Node(6), q = Node(2)
• Output: Node(5) (immediate parent)[1]

Constraints

• Number of nodes: 2 ≤ n ≤ 10^5
• Node values: 0 ≤ Node.val ≤ 10^5 (all unique)
• p != q and both guaranteed in tree
• Tree can be skewed (worst-case height O(n))
• Parent pointers form valid tree structure (no cycles)[1][3]