Lowest Common Ancestor with Parent Pointers (O(1) extra space)

Problem Given two nodes p and q in a tree, each node has a parent pointer (the root has parent = null). Return the Lowest Common Ancestor (LCA) of p and q. The LCA is defined as the lowest node in the tree that has both p and q as descendants (where a node can be a descendant of itself). Requirement: use O(1) extra space (no hash sets or other storage proportional to the tree size). Input/Output Input: node references/pointers p and q. Each node has fields like val and parent. Output: the node reference/pointer of the LCA. Constraints The tree has n nodes and height h. p may equal q. p and q are guaranteed to be in the same tree. Example test scenarios (conceptual) p=5, q=1 -> LCA is 3. p=5, q=4 -> LCA is 5 (ancestor case). p=2, q=2 -> LCA is 2. Nodes in different subtrees of the root -> LCA is the root. Degenerate chain-shaped tree still returns the correct meeting node. Example Input (conceptual) tree: [3,5,1,6,2,0,8,null,null,7,4], p=5, q=1 (with parent pointers) Output 3