The larger binary trees in this chapter were generated automatically by a program.This

Chapter 4, Problem 4.38

(choose chapter or problem)

The larger binary trees in this chapter were generated automatically by a program.This was done by assigning an (x, y) coordinate to each tree node, drawing a circlearound each coordinate (this is hard to see in some pictures), and connecting eachnode to its parent. Assume you have a binary search tree stored in memory (perhapsgenerated by one of the routines above) and that each node has two extra fields tostore the coordinates.a. The x coordinate can be computed by assigning the inorder traversal number.Write a routine to do this for each node in the tree.b. The y coordinate can be computed by using the negative of the depth of thenode. Write a routine to do this for each node in the tree.c. In terms of some imaginary unit, what will the dimensions of the picture be?How can you adjust the units so that the tree is always roughly two-thirds ashigh as it is wide?d. Prove that using this system no lines cross, and that for any node, X, all elementsin Xs left subtree appear to the left of X and all elements in Xs right subtreeappear to the right of X.