4. [30 marks] (Binary tree) Write 1) a non-recursive function to list out the nodes ofa binary tree in preorder, 2) a function to list out the nodes of a binary tree in level- order or breadth first order, that is, to visit the nodes level by level, in each level visit the nodes from left to right. These functions take a pointer to the root node of a tree, and the function prototypes are shown below. / funcs.cpp # include #include "Stack,h" #include "Queue"h" using namespace std; template struct BinaryNode T element; BinaryNode left; BinaryNode* right; BinaryNode (constT&d T):element (d) left-nullptr; right nulipt r ; //print the elements of binary tree in preorder template void preorder (const BinaryNode void breadthfirst (const BinaryNode root) // add your code 3) Write an application program a3q4.cpp that contains a create_binary_tree () function which create the following binary tree (refer to lab 6 exercise click the link). contains main function which call create_binary_tree ) function to create a binary tree, and then call preorder and breadthfirst functions to print the nodes in preorder and level order, respectively. 1) the stack and queue class templates Stack.h and Queue.h, 2) the file funcs.cpp which contains the implementation of functions, 3) the application file a 3q4.cpp containing main) function a script file a3q4result containing result. 4) Here are the sample runs: The preorder: A B D GICEHJK F The level order: A B CDEF GHI J K Hint: The non-recursive preorder traversal uses a stack to store the nodes of the tree. First push the root of the tree in the stack. Then use a while loop: if the stack of nodes is not empty, visit the element of the node at the top position, pop the node, and push the right child and left child of the node. Repeat until the stack is empty. The level-order traversal uses a queue to store the nodes of the tree. First enqueue the root of the tree in the queue. Then use a while loop: if the queue of nodes is not empty, visit the element of the node at the queue front, enqueue the left child and right child of the node. And then dequeue the node. Repeat until the queue is empty