Answer Happy

3. (15%) Let T be a pointer that points to the root of a binary tree. For any node « in the tree, the skewness of r is defined as the absolute difference between the heights of I's left and right sub-trees. Give an algorithm MostSkewed (T) that returns the node in tree T that has the largest skewness. If there are multiple nodes in the tree with the largest skewness, your algorithm needs to return only one of them. You may assume that the tree is non-nuti As an example, for the tree shown in Figure 1, the root node A is the most skewed with a skewness of 3. The skewness of nodes C and F are 1 and 2, respectively. H Figure 1: A tree You can assume that a node is defined with the following structure: struct tree_node { int key /* key value */ tree_node *parent; /* parent pointer */ tree node *left; /left child pointer */ tree node *right, /* right child pointer */ } You may also modify the node structure by adding additional field(s) to it. However, you may not assume that the values of those additional field(s) are available before you execute your algorithm.