-- 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;
}
};
Every time you call inBranch(root, node), you are adding O(# of descendents of root) (See time complexity of Binary Tree Search). I will assume the binary tree is balanced for the first calculation of time complexity, then look at the worst case scenario that the tree is unbalanced.
Scenario 1: Balanced Tree
The number of descendants of a node will be roughly half that of its parent. Therefore, each time we recurse, the calls to inBranch will be half as expensive. Let's say N is the total number of nodes in the tree. In the first call to lowestCommonAncestor, we search all N nodes. In subsequent calls we search the left or right half and so on.
O(N + N/2 + N/4 ...) is still the same as O(N).
Scenario 2: Unbalanced Tree
Say this tree is very unbalanced in such a way that all children are on the left side:
A
/
B
/
C
/
etc...
The number of descendants decreases by only 1 for each level of recursion. Therefore, our time complexity looks something like:
O(N + (N-1) + (N-2) + ... + 2 + 1) which is equivalent to O(N^2).
Is there a better way?
If this is a Binary Search Tree, we can do as well as O(path_length(p) + path_length(q)). If not, you will always need to traverse the entire tree at least once: O(N) to find the paths to each node, but you can still improve your worst case scenario. I'll leave it to you to figure out the actual algorithm!