Description: Creates a class, which will provide functions to access a doubly linked list.Description: Provides a constructer to create an empty tree Calls: get Abbr, Compare ToPseudocode: Project 4Function: Tree Application ClassDescription: Creates a class, which will provide functions to access a doubly linked list.Initialize number of nodes to zero Function: Tree ConstructerDescription: Provides a constructer to create an empty tree Calls: N/A Called by: Main Input Parameters: N/A Returns: N/ASet root to null Function: InsertDescription: Method to insert a node into the treeCalls: get Abbr, Compare ToCalled by: MainInput Parameters: tree nodeReturns: N/AGet abbr of tree nodeIf root is null Set root to tree nodeElse Create current node and set to root of tree Create parent node While true Set parent node to current If abbr is less than abbr of current nodeSet current to current.leftChild If current is null Set left child of parent to tree node ReturnEnd If ElseSet current to current.rightChildIf current is null Set right child of parent to tree node ReturnEndIf End Else End WhileEnd ElseFunction: Traverse Description: Traverses the tree based on type of scan requiredCalls: LNR Recursive, NLR Recursive, NLR Iterative, RNL IterativeCalled by: Main Input Parameters: type of traversalReturns: N/ASwitch (Input traverse type)Case 1: Print tree using LNR recursive scan Print header consisting of node num, abbr, population and state Call LNR Recursive method to traverse tree staring at the root Break;Case 2: Print tree using NRL recursive scan Print header consisting of node num, abbr, population and state Call NRL Recursive method to traverse tree staring at the root Break;Case 3: Print tree using NLR Iterative scan Print header consisting of node num, abbr, population and state Call NLR Iterative method to traverse tree staring at the root Break;Case 4: Print tree using RNL Iterative scan Print header consisting of node num, abbr, population and state Call RNL Iterative method to traverse tree staring at the root Break;End switchFunction: LNR RecursiveDescription: Performs a In order traversal on the tree using recursion Calls: LNR Recursive (itself), display NodeCalled by: Traverse Input Parameters: tree node Returns: N/A If the tree node is not null Call itself to perform function on left child Display the node Call itself to perform function on right childEndIfFunction: NLR RecursiveDescription: Performs a In order traversal on the tree using recursion Calls: NLR Recursive (itself), display NodeCalled by: Traverse Input Parameters: tree node Returns: N/A If the tree node is not null Display the node Call itself to perform function on left child Call itself to perform function on right childEndIfFunction: RNL IterativeDescription: Performs a RNL Iterative scan on the tree Calls: is Empty, Stack constructor, push, pop, display NodeCalled by: Traverse Input Parameters: tree node Returns: N/A Create stack of type tree nodeSet node to the root of treeWhile true While node isn’t null Push node onto stack Set node to right child of node End while If the stack is not empty Pop last item on stack Display the node Set node to left child of node End if Else Break; End whileFunction: NLR IterativeDescription: Performs a non recursive Pre Order traversal on the tree Calls: is Empty, Stack constructor, push, pop, display NodeCalled by: Traverse Input Parameters: tree node Returns: N/A Create stack of type tree nodeSet node to the root of treeWhile true While node isn’t null Display the node Push node onto stack Set node to left child of node End while If the stack is not empty Pop last item on stack Set node to right child of node End if Else Break; End whileFunction: DeleteDescription: Deletes given node in the tree Calls: Compare To, get SuccessorCalled by: MainInput Parameters: abbreviation Returns: true or false Set current node to rootSet parent node to rootSet is left child to true//find node in the treeWhile there is no match Set parent to current If given abbreviation is less than current Set is left child to true Set current to current.leftChild End if Else Set is left child to false Set current to current.rightChild End ElseIf current is null Returns false Print that the state could not be found End IfEnd While//if the node has no children… if current has no left child and no right child if current is root set root to null else if it is left child (check Boolean variable) set left child of parent to null else set right child of parent to null end if//if node only had one child..Else if node does not have right child If current is root Set root to left child of current Else if it is left child Set parent.leftChild to current.leftChild Else Set parent.rightChild to current.leftChild//if node has two children… Else Get the successor of current node (call get successor method) If current is root Set root to successor Else if current is left child Set parent.leftChild to successor Else Set parent.rightChild to successorSet successor.leftChild to current.leftChildEnd ElsePrint that state has been deletedReturn trueFunction: get successorDescription: gets the next in order successor of the node being deleted Calls: N/ACalled by: DeleteInput Parameters: nodeReturns: node Set successor parent to nodeSet successor to nodeSet current to node.rightChildWhile current is not null Set successor parent to successor Set successor to current Set current to current.leftChildEnd While If successor isn’t right child of node Set successor parent to successor.rightChild Set successor.rightChild to node.rightChild End ifReturn successorFunction: FindDescription: finds a node in the tree using abbreviation Calls: N/ACalled by: MainInput Parameters: abbreviation Returns: true or falseSet current node to rootSet searched nodes to zero While there is no match If given abbreviation is less than current Set current to current.leftChild Increment searched nodes End if Else Set current to current.rightChild Increment searched nodes End ElseIf current is null Return false Print node couldn’t be foundEnd ifEnd WhileReturn truePrint node was