3. Assume that we visit the nodes in a binary tree in the order that they are numbered in heapsort, but you may only move directly to nodes connected by tree edges. You want to start at the root and end at the root, and visit all nodes up to and including node n. You will have to visit intermediate nodes multiple times. For example, assume that you want to visit up to node 3 then you will visit the nodes in order 1, 2, 1, 3, 1. If you want to end at node 7 you will visit the nodes in order 1, 2, 1, 3, 1, 2, 4, 2, 5, 2, 1, 3, 6, 3, 7, 3, 1. In the first example you will cross edges 4 times, in the second example you will cross edges 16 times. We want to calculate how many edge crossings there are. To keep things simple we will only consider visiting up to the last node of a level. Then we can calculate by levels rather than node numbers. There are a number of ways of solving this problem but we want to do it with recurrences. Levels are normally numbered 0 for just the root (node 1), 1 for nodes 2 and 3, 2 for nodes 4, 5, 6, and 7, etc. (a) Write a recurrence (as a function of k) for the number edges crossed when completing k levels (levels ( to k 1). (Note that n = (b) Solve the recurrence (as a function of k) using the tree method. Show your work. (d) Rewrite your answer in terms of n. 2k 1.)