Greetings,
I have some problem with such needed algorithms I know the outlines but I do not know how to implement especially with recursion :(
Consider a binary tree T of n nodes where every node has 4 fields:
LABEL (an integer between 1 and n representing the label of the node),
lchild (a pointer to the left child),
rchild (a pointer to the right child),
and parent (a pointer to the parent).
Let H[1...n], C[1...n] and D[1...n,1...n] be three arrays.
a) Give a recursive algorithm that takes T as input and computes the depth of every node.
The algorithm should store the depth of node of LABEL i in H[i].
b) Give a recursive algorithm that takes T as input and computes the number of descendants of every node.
The algorithm should store the number of descendants of node of LABEL i in C[i].
c) Define the distance between any two nodes i and j in the tree to be the number of edges of the shortest path between i and j.
Assume that the depth H[i] of every node i has been computed. Let p be a pointer to a node of LABEL I in T.
Give a recursive algorithm that takes T and p as input to compute the distance between node p and every other node.
The algorithm should store the distance between node p and any node of LABEL j in D[I,j].