Lowest common ancestor of a binary tree ii

Tree Depth-First Search Binary Tree

69.6% acceptance

Mar 31, 2026

702

Given the root of a binary tree, return the lowest common ancestor (LCA) of two given nodes, p and q. If either node p or q does not exist in the tree, return null. All values of the nodes in the tree are unique. According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a binary 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)". A descendant of a node x is a node y that is on the path from node x to some leaf node.

Solution

C++

Time O(n)

Space O(n)

LeetCode

solution.cpp

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    bool foundP = false, foundQ = false;
    TreeNode* ans = dfs(root, p, q, foundP, foundQ);
    return (foundP && foundQ) ? ans : nullptr;
  }
  
private:
  TreeNode* dfs(TreeNode* node, TreeNode* p, TreeNode* q, bool& foundP, bool& foundQ) {
    if (!node) return nullptr;
    TreeNode* left = dfs(node->left, p, q, foundP, foundQ);
    TreeNode* right = dfs(node->right, p, q, foundP, foundQ);
    if (node == p) { foundP = true; return node; }
    if (node == q) { foundQ = true; return node; }
    if (left && right) return node;
    return left ? left : right;
  }
};