Question

1. Assume that a tree is represented by X, lef t(X), right(X) and possibly other satellite data that we ignore. Write an algorithm that checks if for any X, if hL is the hight of lef t(X) and hR is the height of right(X), then the algorithm return ”correct” if and only if for every vertex |hL−hR| ≤ 1. Namely, no left tree of any vertex is higher by two or more than the right tree of the vertex, and vise-versa. Remember to analyze the running time

Answer 1

Here is an algorithm for the given task. The algorithm works recursively by going over all the vertices in a top-down manner and checking for the condition that |hL - hR| <= 1

Maintain a global array heights[]

Algorithm checkHeight(X):

if(X == null) heights[X] = 0; return "correct"

if(checkHeight(left(X)) && checkHeight(right(X))):

hL = heights[left(X)]

hR = heights[right(X)]

if(|hL - hR| <= 1) return "correct";

return "false";

Running Time:

The algorithm just goes once over each vertex, and hence runs in O(n) time.

You can comment below the answer in case of any doubts and I will be happy to help.

Please give a thumbs up if the answer could be of help!

All the best!