I need help with writing a java code for this project, I$\text{'}$m $$using intelliji. The third programming project involves writing a program to read in the preorder representation of a binary tree and determine whether it is a balanced binary search tree. Given the binary tree Its preorder representation would be $(53(28(11**)(41**))(83(67**)*)).$ The asterisks represent null children. The program should repeatedly prompt the user for a binary tree. It should then display the tree using indentation. For the above tree, its indented representation would be as follows: $532811418367$ It should then categorize the binary tree in one of three ways: $$ It is not a binary search tree $$ It is a balanced binary search tree $$ It is a binary search tree but it is not balanced If the tree is not a balanced binary search tree, a binary search tree containing the same set of values should be constructed and displayed in the indented format shown above. It is not expected that the existing tree be rebalanced, just that a new tree with the same set of values be constructed. Then the height of the original tree and the balanced binary search tree should be displayed. Shown below is a sample session that involves each of the above cases: Enter a binary tree: $(53(28(11**)(41**))(83(67**)*))532811418367$ It is a balanced binary search tree More trees? Y or N: Y Enter a binary tree: $(63(51(20(13**)*)*)*)63512013$ It is a binary search tree but it is not balanced $20135163$ Original tree has height $3$ Balanced tree has height $2$ More trees? Y or N: Y Enter a binary tree: $(13(53**)(11(59**)*))13531159$ It is not a binary search tree $13115359$ Original tree has height $2$ Balanced tree has height $2$ More trees? Y or N: N In addition, the program should verify that the tree input has valid syntax. Each of the following errors should be detected; $$ Incomplete Tree $$ Data is Not an Integer $$ Extra Characters at the End $$ Missing Left Parenthesis $$ Missing Right Parentheses The program should consist of three classes. The first class should be the class that defines the binary tree. It should be an immutable class with the following public methods: $$ A constructor that accepts a string containing the preorder representation of a binary tree and constructs a binary tree $$ A constructor that accepts an array list of integers and constructs a balanced binary search tree containing those values $$ A method that outputs the binary tree in indented form $$ A method that returns whether the tree is a binary search tree $$ A method that returns whether the tree is balanced $$ A method that returns the height of the tree $$ A method that returns an array list of the values in the tree Additional private methods may be added as needed. The second class should be a class that defines a checked exception that is thrown when a tree with invalid syntax is input. The third class is the class that contains the main method and accepts the user input and displays the results. The third programming project involves writing a program to read in the preorder representation of a binary tree and determine whether it is a balanced binary search tree. Given the binary tree shown below:

Its preorder representation would be $(53(28(11**)(41**))(83(67**)*)).$ The asterisks represent null children. The progrum should repeatedly prompt the user for a binary tree. It should then display the tree using indentation. For the above tree, its indented representation would be as follows;

$53$

$28$

$12$

$41$

$83.$

$67$

It should then categorize the binary tree in one of three ways:

$-$ It is not a binary search tree

$-$ It is a balanced binary search tree

$-$ It is a binary search tree but it is not balanced

If the tree is not a balanced binary search tree, a binary search tree containing the same set of values should be constructed and displayed in the indented format shown above. It is not expected that the existing tree be rebalanced, just that a new tree with the same set of values be constructed. Then the leight of the original tree and the balanced binary search tree should be displayed.

Shown below is a sample session that involves each of the above cases: $```$

Enter a binary tree: $(53(28(11**)(41**))(83(67**)*))$

$53$

$28$

$11$

$41$

$83$

$67$

It is a balanced binary search tree

More trees? Y or N: Y

Enter a binary tree: $(63(51(20(13**)*)*)*)$

$63$

$51$

$20$

$13$

It is a binary search tree but it is not balanced

$20$

$13$

$51$

$63$

Original tree has height $3$

Balanced tree has height $2$

More trees? Y or N: Y

Enter a binary tree: $(13(53**)(11(59**)*))$

$13$

$53$

$11$

$59$

It is not a binary search tree

$13$

$11$

$53$

$59$

Original tree has height $2$

Balanced tree has height $2$

More trees? Y or N: N

$```$ In addition, the program should verify that the tree input has valid syntax. Each of the following errors should be detected;

$-$ Incomplete Tree

$-$ Data is Not an Integer

$-$ Extra Characters at the End

$-$ Missing Left Parenthesis

$-$ Missing Right Parentheses

The program should consist of three classes. The first class should be the cl $-$ A method that o