Let T be a binary tree with height h. Recall that a node u is an ancestor of a n
ID: 3850679 • Letter: L
Question
Let T be a binary tree with height h. Recall that a node u is an ancestor of a node v if the path from v up to the root of T includes u. Note that any node v is considered an ancestor of itself. For two nodes v_1 and v_2, the lowest common ancestor is the lowest (that is, furthest from the root) node u such that u is an ancestor of both v_1 and v_2. The diagrams below show the lowest common ancestor (denoted by u) of several v_1, v_2 pairs. Give pseudocode for a O(h) algorithm to find and return the lowest common ancestor of two nodes v_1 and v_2. Include a brief justification for the running time of your solution.Explanation / Answer
One of the easiest way is to find the path, store it and then traverse both the paths. In this way we can't go beyond O(h). How? A path to a node can have maximum of tree's height element, not greater than that. Hence, we traverse for O(h) or less than height of tree for two times i.e. O(2h). Then we compare the path, which again can't be greater than O(h). In total our complexity would turn out to be Big-Oh of 3h and as contant is almost ignored everytime, complexity reduces to O(h). Another method is going recusrively that will save us space.
Consider the following pseudo-code:
struct Tree *find(struct Tree* root, int value1, int value2)
if root is NULL return NULL
if root->key is value1 or value2
return root
Tree *left_find = find(root->left, value1, value2)
Tree *right_find = find(root->right, value1, value2)
if(left_find && right_find) return root;
return (left_find != NULL)? left_find : right_find
The above function just returns a pointer the lowest common ancestor of the both the values passed. We start from the root and if any of the value matches, then we return root only. In case, it doesn't match then we recursively traverse right and left both. If both the sub trees contain the value then root is the lowest common ancestor otherwise if both the keys lie in the left part then left has the lowest common ancestor and if not then right part has it.
Now, this recursive function just traverses the array in bottom-up function and hence can't go beyond the height of the tree which gives us the complexity of O(h).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.