Let $T$ be a rooted binary tree dynamically implemented with $n$ nodes, and let $v$ be a node of $T$. The level ancestor query $LA(v,d)$ returns the ancestor of node $v$ at depth $d$, where the depth of a node $m$ in a tree is the number of edges on the shortest path from the root of the tree to node $m$.
Example: In the following tree, $LA(h,2) = d$ since the ancestor of node $h$ of depth 2 is the node $d$.
Given the root of a binary tree dynamically implemented, a pointer to a node $v$ in the tree, and a depth $d$, write a function that returns a pointer to $v$'s level ancestor at depth $d$.
Restrictions:
- Time complexity of your function: $O(n)$, where $n$ is the number of nodes.
- Each node should be traversed at most once.
- Usage of arrays, stacks and queues is not allowed.
Difficulty level
This exercise is mostly suitable for students
typedef char element;
typedef struct node
{
element data;
struct node *left,*right;
} *Btree;
int find(Btree T, Btree v)
{
if(!T) return 0;
if(T->data == v->data) return 1;
return find(T->left,v) || find(T->right,v);
}
Btree LA(Btree T, Btree v, int depth)
{
Btree L,R;
if(T && depth==0 && find(T,v))
return T;
if(T && depth>0)
{
L = LA(T->left,v,depth-1);
R = LA(T->right,v,depth-1);
if(!L && !R) return NULL;
if(L) return L;
return R;
}
return NULL;
}Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Removing a sequence of 3 characters from a string