IN JAVA CODING

Part I: Tree Construction and Validation

The program shall have a method called makeTree$(),$ that will take a String as a parameter,

representing the prefix expression provided by the computer user. This method will:

$1.$ validate if the given expression is valid. The method will throw a InvalidSyntaxExpression$1$

in case the expression contains blank spaces or the parenthesis are not matching $($i$.$e$.,$ open

and closing parenthesis$).$

$2.$ create a binary tree based on the given expression. The rules for the tree can be found on Part

II$.$

The method shall return a Node representing the root of this tree.

Part II: Prefix Expressions

The expression given by the computer user represents a binary tree, where

each node of the tree contains a single alphanumeric character.

no blank spaces are allowed

Each tree is enclosed in parentheses.

Inside those parentheses, after the single character are either $0,1,$ or $2$ subtrees also enclosed

in parentheses.

In the case that only one subtree is present, it is the left subtree and when two are present,

they represent the left and right subtrees.

You are responsible to create the InvalidSyntaxExpression class and handle the potential exception

For example, if the expression looks like this:

$($A$($C$($k$)(2))($N$(24)))$

Part III: Methods

Create a program called BinaryTreeExpression.java, where the following methods are implemented:

$1.$ getHeight$()$: The height of a tree is the maximum level of all of its nodes, i$.$e$.,$ the largest

path from the root to the largest leaf

$2.$ size$()$: it will return an int representing the total number of nodes in the tree

$3.$ totalParents$()$: it will return an int representing the total number of parents in the tree.

A parent is a node having one or two nodes as children

$4.$ totalLeaves$()$: it will return an int representing the total number of leaves in the tree. A

node is considered to be a leaf if it has no dependencies, thus no children

$5.$ isBalanced$()$: returns true if the binary tree is balanced, meaning that for each node in the

binary tree, the height from the left and right subtree is at most one level. Otherwise the

method shall return false

$6.$ isFull$()$: A full binary tree is full if each node is either a leaf or possesses exactly two child

nodes

$7.$ getInorder$()$: it will return a String representing the inorder transversal algorithm