Answer Happy

3. (15%) Let T be a pointer that points to the root of a binary tree. For any node x in the tree, the skewness of r is defined as the absolute difference between the heights of x'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-null. 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. B E F H D K 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.