Programming ProjectsWriting programs to solve the Programming Projects helps to solidify your under standing of the material and demonstrates how the chapter's concepts are applied. $($As noted in the Introduction, qualified instructors may obtain completed solutions to the Programming Projects on the publisher's Web site.$)8\mathrm{.}1$ Start with the tree.java program $($Listing $8\mathrm{.}1)$ and modify it to create a binary tree from a string of letters $($like A$,$ B$,$ and so on$)$ entered by the user. Each letter will be displaved in its own node. Construct the tree so that all the nodes that contain letters are leaves. Parent nodes can contain some non$-$letter symbol like $+.$ Make sure that every parent node has exactly two children. Don't worry if the tree is unbalanced. Note that this will not be a search tree: there's no quick way to find a given node. You may end up with something like this:EDAB trees. $($A group of unconnected t One way to begin is by making an array of trees. $($A is called a forest.$)$ Take each letter typed by the user and put it in each of these nodes and put it in a tree, where it will be the root. Now put all making a new tree these one$-$node trees in the array. Start by making and two of the one$-$node trees as its children. Then keep adding ono f it's an unbalanced from the array to this larger tree. Don't worry if tree You can actually store this intermediate tree in the array by writing over a cell whose contents have already been added to the treeThe routines find$(),$ insert$(),$ and delete$(),$ which apply only to search fre can be deleted. Keep the displayTree$()$ method and the traversals because they will work on any binary tree$\mathrm{.}8\mathrm{.}2$ Expand the program in Programming Project $8\mathrm{.}1$ to create a balanced tree way to do this is to make sure that as many leaves as possible appear in the bottom row. You can start by making a three$-$node tree out of each pair of on node trees, making a new $+$ node for the root. This results in a forest of three node trees. Then combine each pair of three$-$node trees to make a forest of seven$-$node trees. As the number of nodes per tree grows, the number of tres shrinks, until finally there is only one tree left.Again, start with the tree. iava program and make a tree from characters typ by the user. This time, make a complete tree$-$one that is completely full except possibly on the right end of the bottom row. The characters should be ordered from the top down and from left to right along each row, as i if writing a letter on a pyramid. $($This arrangement does not tcorrespond to any of the three traversals we discussed in this chapter.$)$ Thus, the string ABCDEFGHIJ would be arranged asAD EGOne way to create this tree is from the top down, rather than the bottom up in the previous two Programming Projects. Start by creating be the root of the final tree. If you think of the a node which will the nodes as being numbered in the same order the letters are arranged, with $1$ at the root, then any node numbered n has a left child numbered $2*$n and a You might use a recursive routine that makes right child numbered $2*$n$+1.$ then calls itsel for each child. The nodes don't need to be created in the same two children and arranged on the tree. As in the previous Pr order they are the search$-$tree routines from the Tree class. you can jettison Programming Projects,