Create an executable program based on the instructions below: Binary tree construction

The steps below show how to build a binary tree from the input expression of the preorder

representation of the binary tree.

Consider preorderExp as the input expression.

$1.$ Make sure preorderExp is valid.

$2.$ Remove all parenthesis from preorderExp.

$3.$ Remove all spaces from preorderExp and obtain nodeValues, an array of String containing

node values. This may be achieved, for example, by using the method split.

$4.$ Invoke method makeTree as:

root $=$ makeTree$($nodeValues$,0)$;

$5.$ Define the makeTree method recursively, given that the values in nodeValues represent the

preorder tree traversal:

Node makeTree$($String$[]$ nodeValues, int arrayIndex$)\{...\}$

Attention should be paid to string $*$ which represents the base case of recursive processing,

when a tree branch is completed, and control of tree construction resumes to a higher level.

Notes

$1.$ Preorder tree traversal is in$-$depth traversal, visiting first the node and going in depth on left

subtree as much as possible before visiting the right subtree.

$2.$ Class Node defines the instance variables value of type int and references left and right of

type Node.

$3.$ root is a variable of type Node

$4.$ arrayIndex is stepping through the nodeValues, indicating the array value to be processed by

makeTree method.

$5.$ To make sure you build the binary tree correctly, I suggest you define a private method

preorderTraversal that displays the value of tree nodes. These values should match $($in the

same order$),$ the values in the input expression of preorder representation of the binary tree.

$6.$ Use debugging techniques $($see class announcement of August $15)$ to fix the errors if

necessary.