# Share C++/C# 24ms recursive solution

• C++ version

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root)
return NULL;
if(root == p || root == q)
return root;
// Check if left contains p or q
TreeNode* left = lowestCommonAncestor(root->left, p, q);
// Check if right contains p or q
TreeNode* right = lowestCommonAncestor(root->right, p, q);
// if left and right containsp or q the it'sthe LCA
if(left && right)
return root;
return left ? left : right;
}

C#version

public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null)
return null;
if(root == p || root == q)
return root;
var left = LowestCommonAncestor(root.left, p, q);
var right = LowestCommonAncestor(root.right, p, q);
if(left != null && right != null)
return root;
return left ?? right;
}

• what happens if p or q is not part of the tree?

• Good question: it will return p or q because the solution assumes that both p and q are part of the tree.
The following code handles the case where only p or q are present

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL)
return NULL;
TreeNode* result = LowestCommonAncestorHelper(root, p, q);
if (result != p && result != q)
return result;
if (result == p && LowestCommonAncestorHelper(root, NULL, q) == q)
return result ;
if (result == q && LowestCommonAncestorHelper(root, NULL, p) == p)
return result;
return NULL;
}

TreeNode* LowestCommonAncestorHelper(TreeNode* root, TreeNode* p, TreeNode* q)
{
if (root == NULL)
return NULL;
if (root == p || root == q)
{
return root;
}
TreeNode* left = LowestCommonAncestorHelper(root->left, p, q);
TreeNode* right = LowestCommonAncestorHelper(root->right, p, q);
if (left != NULL && right != NULL)
return root;
return left ? left: right;
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.