Lowest common ancestor of a binary tree iii

Hash Table Two Pointers Tree Binary Tree

83.0% acceptance

Mar 31, 2026

1538

Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA). Each node will have a reference to its parent node. The definition for Node is below: class Node { public int val; public Node left; public Node right; public Node parent; } According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)."

Solution

C++

Time O(n)

Space O(1)

LeetCode

solution.cpp

/*
// Definition for a Node.
class Node {
public:
  int val;
  Node* left;
  Node* right;
  Node* parent;
};
*/

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