Build a binary tree in Java with given the depth N as parameter, this method recursively

builds a full binary search tree of depth N such that the nodes store the integers

1, 2, 3, , 2^(N+1) 1

Hints.

- The method returns the root of the tree it built

- The method shall be double recursive, a recursive call must apply (with decreased

depth) to both the left link and right link of the current node

- depth is naturally the control parameter and the base case is depth = = 0

- it may be helpful to add another sliding parameter to the method, the top number

stored in the root of the current sub-tree

- Take a good look at Figure 1, it shows the solution of case N = 3 and it helps to

understand the distribution of the given values in a binary search tree

Add an application class Test to test.

4 12 0 10 14 1357 9 13 15