Code Implementation

# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        a, b = p, q
        # Traverse up both nodes, switching to the other node when reaching root
        while a != b:
            a = a.parent if a else q
            b = b.parent if b else p
        return a
      

// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
    Node(int _val) {
        val = _val;
        left = nullptr;
        right = nullptr;
        parent = nullptr;
    }
};

class Solution {
public:
    Node* lowestCommonAncestor(Node* p, Node* q) {
        Node* a = p;
        Node* b = q;
        while (a != b) {
            a = a ? a->parent : q;
            b = b ? b->parent : p;
        }
        return a;
    }
};
      

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
    public Node(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}
*/

class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        Node a = p, b = q;
        while (a != b) {
            a = (a != null) ? a.parent : q;
            b = (b != null) ? b.parent : p;
        }
        return a;
    }
}
      

/**
 * // Definition for a Node.
 * function Node(val) {
 *   this.val = val;
 *   this.left = this.right = this.parent = null;
 * }
 */

/**
 * @param {Node} p
 * @param {Node} q
 * @return {Node}
 */
var lowestCommonAncestor = function(p, q) {
    let a = p, b = q;
    while (a !== b) {
        a = a ? a.parent : q;
        b = b ? b.parent : p;
    }
    return a;
};
      

Problem Description

You are given two nodes, p and q, of a binary tree. Each node contains a pointer to its parent node (i.e., node.parent), in addition to its left and right children. Your task is to find the lowest common ancestor (LCA) of these two nodes. The LCA of two nodes 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).

• Every node has a unique value.
• Both p and q are guaranteed to exist in the tree.
• The tree is not necessarily a binary search tree.
• There is exactly one valid solution for each input pair.

Thought Process

The main challenge is to find the lowest common ancestor of two nodes in a binary tree where each node has a parent pointer. Unlike the classic LCA problem (where you start from the root), here you can move up from any node to the root using the parent pointer.

A brute-force approach would be to traverse up from one node (p), record all ancestors in a set, then traverse up from the other node (q) and return the first ancestor found in the set. This works, but can be improved.

Thinking further, if you consider the paths from p and q to the root as two linked lists, the problem becomes similar to finding the intersection node of two singly linked lists. By traversing up both at the same speed and switching to the start of the other list when reaching the end, you guarantee that both pointers will meet at the LCA.

Solution Approach

The optimized solution leverages the parent pointers and the analogy to linked list intersection:

1. Initialize two pointers, a and b, at nodes p and q respectively.
2. Traverse up the tree by moving each pointer to its parent. If a pointer reaches null (root's parent), reset it to the other starting node.
3. Continue moving both pointers up (switching as described) until they meet. The meeting point is the LCA.

This works because both pointers traverse the same number of steps (the sum of the distances from p and q to the root), ensuring they sync up at the LCA.

• Why not use a hash map? Using a hash set to store ancestors works but uses extra space. The two-pointer approach is more elegant and uses constant space.
• Why does switching pointers work? When one pointer reaches the root, it starts from the other node, so both traverse the combined lengths and will align at the LCA.

Example Walkthrough

Consider the following tree:

        3
       / \
      5   1
     / \   \
    6   2   8
  

Suppose p = 6 and q = 8.

1. Pointer a starts at 6, pointer b starts at 8.
2. Move both up: a goes to 5, b goes to 1.
3. Next: a to 3, b to 3.
4. They meet at node 3, which is the LCA.

If the depths are different, the switching ensures both pointers traverse the same total path length and meet at the LCA.

Time and Space Complexity

• Brute-force:
  • Time: O(h), where h is the height of the tree (walk up ancestors for both nodes)
  • Space: O(h), for storing ancestors in a set
• Optimized (two-pointer):
  • Time: O(h), since each pointer traverses at most 2h steps (height of tree)
  • Space: O(1), no extra data structures needed

The optimized approach is both time and space efficient.

Summary

The key insight is to treat the ancestor chain as a singly linked list and use two pointers to find their intersection (lowest common ancestor). By leveraging parent pointers and pointer switching, we achieve an elegant, constant-space solution that is efficient and easy to implement.