3. (6 points - Correctness) K-d Trees. Let Tbe the 2-d tree built from the following sequence of points with (x,y) coordinates: (8,9):(12,7):(6,8):(14,11);(13,6):(4,12) (a) Draw the tree T, using the typical visualization scheme for binary trees - i.e. do not draw a K-d tree grid. Make sure to include the coordinates of the nodes, as seen in lecture (i.e. root should be a circle with (8,9) inside it) (b) Now, say we're querying for the nearest neighbor of point (11,8). Assume a recursive method findNN exists, with all the necessary arguments to recursively find the nearest neighbor. Which nodes in the tree are evaluated as potential nearest neighbors of (11,8)? Make sure to include the root node in your calculations. We only care about concrete nodes, recursive calls of findNN on null nodes don't matter (c) Finally, derive the worst case time complexity of the build tree operation shown in lecture (BuildRecurse), for building a K-d tree with n points. You can assume that there no duplicate points. Your result should be a function of nand must be tighter than O(n3), but does not have to be the tightest upper bound. Show and simplify your work