Find the Shared Ancestor Using Parent Links

### Problem `p` and `q` are distinct nodes in the same binary tree. Each `Node` has fields `val`, `left`, `right`, and `parent`; the root’s parent is null. Return the node pointer for their lowest common ancestor, counting a node as its own descendant. The function receives the two node pointers, not the root or an array encoding. ```cpp class Solution { public: Node* lowestCommonAncestor(Node* p, Node * q); }; ``` ### Examples **Example 1:** ```text Tree: root value 10 has children 6 and 14; node 6 has child 4. p points to node 4; q points to node 14. Output: pointer to node 10 Explanation: Their first shared ancestor is the root. ``` **Example 2:** ```text Tree: root value 8 has child 3, which has child 1. p points to node 3; q points to node 1. Output: pointer to node 3 Explanation: An input node can itself be the lowest common ancestor. ``` ### Constraints - The tree has `2..10^5` nodes. - Node values are unique integers in `[-10^9,10^9]`. - `p != q`, and both nodes exist in the tree. ### Clarifying Questions The result is an existing Node pointer, preserving identity. Parent links are supplied and must agree with the binary tree; they are not a request to rebuild a tree from values. ```hint Inspect the structure What does it mean to return the same existing node when one input is already an ancestor of the other? ``` ### Reasoning checkpoints - Use parent links without requiring the root argument. - Preserve pointer identity and ancestor-self behavior. ### Optional extensions What preprocessing would help if many LCA queries referred to this same tree?