Interview Questions
Find common ancestor in tree
Each node in the tree has a pointer to parent and pointers to all children nodes. On input you received two nodes from the tree and your algorithm has to return closest common node between these two nodes.
View Solution
Algorithm concept
Each node you receive as an input can be at different level (high) in a tree. The tree has a common parent, so all nodes, when going "up" to the parent will end up in a top node of a tree. The best way to solve this problem is to navigate each node up, going to parent, then parent's parent, etc. until both pointers meet.
In order to do this however and find common parent, you need to first ensure that both nodes are on the same high, so first you need to calculate high of each node.
Complexity
This algorithm has complexity depends on the tree high. Worst case it is O(n), for balanced binary tree it is O(logn), as logn is the height of balanced binary tree.
Solution
struct node
{
int value;
node *left;
node *right;
node *parent;
};
int getNodeDepth(node *child)
{
int depth = 0;
node *currentNode = child;
while (currentNode != nullptr)
{
currentNode = currentNode->parent;
depth++;
}
return depth;
}
struct node *findCommonParent(node *child1, node *child2)
{
// first lets calculate depth of both children
int child1Depth = getNodeDepth(child1);
int child2Depth = getNodeDepth(child2);
// make depth of parents equal
while (child1Depth > child2Depth)
{
child1 = child1->parent;
child1Depth--;
}
while (child2Depth > child1Depth)
{
child2 = child2->parent;
child2Depth--;
}
// walk up until we hit the same node
while (child1 && child2 && (child1 != child2)
{
child1 = child1->parent;
child2 = child2->parent;
}
if (!child1 || !child2) return nullptr;
return child1;
}