-- The following lowestCommonAncestor
function finds the Lowest Common Ancestor of two nodes, p
and q
, in a Binary Tree (assuming both nodes exist and all node values are unique).
class Solution {
public:
bool inBranch(TreeNode* root, TreeNode* node)
{
if (root == NULL)
return false;
if (root->val == node->val)
return true;
return (inBranch(root->left, node) || inBranch (root->right, node));
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL)
return NULL;
if (root->val == p->val || root->val == q->val)
return root;
bool pInLeftBranch = false;
bool qInLeftBranch = false;
pInLeftBranch = inBranch (root->left, p);
qInLeftBranch = inBranch (root->left, q);
//Both nodes are on the left
if (pInLeftBranch && qInLeftBranch)
return lowestCommonAncestor(root->left, p, q);
//Both nodes are on the right
else if (!pInLeftBranch && !qInLeftBranch)
return lowestCommonAncestor(root->right, p, q);
else
return root;
}
};
p
andq
.O (sqrt (N))
, i.e. naive (brute force) algorithm. Bender M., Farach-Colton M. works inO(log(N))