20 views

In a binary tree $T$, for a node $v$, the $\text{LEFT-HEIGHT} (v)$ is the length of the longest path from $v$ to any leaf in the left subtree of $v$. If $v$ has no left child then $\text{LEFT-HEIGHT} (v)=0$. The $\text{RIGHT-HEIGHT} (v)$ is defined accordingly.

A node $v$ is said to be properly balanced if $$\mid \operatorname{LEFT-HEIGHT}(v)-\text { RIGHT-HEIGHT }(v) \mid \leq 1 \text {. }$$ Design an efficient algorithm that, given a binary tree, enumerates all the nodes which are properly balanced.

1 vote