Algorithms question, don't particularly know where to start.

3. We define the height(v) of a tree rooted at v to be the length of the longest path from the root to a leaf (if two nodes are connected by a path, the length of the path is the number of edges along this path). An alternative way of defining the height h(t) of a tree t is if t is empty or just a single node (i.e. the root is also the single leaf), h(t)-O0 if t is not just a single node then h(t) is one plus the maximum of the heights of its children. (a) (15 points) Give e for a DIVIDE-AND-CONQUER algorithm to find the height of a binary tree. For a tree t, you can include in your pseudo-code statements like 'if t is a single node," "t's left subtree," "t's right subtree." (b) (5 points) Suppose that in the binary tree given for the initial input all of the nodes have no right child (the binary tree is degenerate). Give a recurrence for T(n) where T(n) is the time complexity of your algorithm when the tree has n nodes. Then give a tight asymptotic bound for T(n) (c) (5 points) Now suppose that the binary tree given for the initial input is a complete binary tree in which all leaves have the same depth. For such a tree the left and right subtree have the same number of nodes. Give a recurrence T(n) expressing the run time of your algorithm when the tree has n nodes. Then give a tight asymptotic bound for T(n) 3. We define the height(v) of a tree rooted at v to be the length of the longest path from the root to a leaf (if two nodes are connected by a path, the length of the path is the number of edges along this path). An alternative way of defining the height h(t) of a tree t is if t is empty or just a single node (i.e. the root is also the single leaf), h(t)-O0 if t is not just a single node then h(t) is one plus the maximum of the heights of its children. (a) (15 points) Give e for a DIVIDE-AND-CONQUER algorithm to find the height of a binary tree. For a tree t, you can include in your pseudo-code statements like 'if t is a single node," "t's left subtree," "t's right subtree." (b) (5 points) Suppose that in the binary tree given for the initial input all of the nodes have no right child (the binary tree is degenerate). Give a recurrence for T(n) where T(n) is the time complexity of your algorithm when the tree has n nodes. Then give a tight asymptotic bound for T(n) (c) (5 points) Now suppose that the binary tree given for the initial input is a complete binary tree in which all leaves have the same depth. For such a tree the left and right subtree have the same number of nodes. Give a recurrence T(n) expressing the run time of your algorithm when the tree has n nodes. Then give a tight asymptotic bound for T(n)