Header InformationYou must store some initial information in the compressed file that will be used by the decompression/decoding program. Basically, you must store the tree that is used to compress the original file. This is because the decompression program needs this exact same tree in order to decode the data. The header information contains:• The topology of the Huffman coding tree. To store the tree at the beginning of the file, we use a post-order traversal, writing each node visited. When you encounter a leaf node, you write a 1 followed by the ASCII character of the leaf node. When you encounter a non-leaf node, you write a 0. To indicate the end of the Huffman coding tree, we write another 0.• The total number of characters in the input file, followed by an end-marker.7Consider the string "go go gophers", the header information is "1g1o01s1 01e1h01p1r0000013#", where "#" is the end-marker specifying the end of the header file. The post-order traversal of the Huffman coding tree gives us "1g1o01s1 01e1h01p1r0000". Another "0" separates the topology from "13", which is the number of characters in the input file.For the string "streets are stone stars are not", the header information is "1t1a1r001n1o01 01e1s000031#". The resulting tree would look like thisThe numbers below each leaf node corresponds to the frequencies for each character appears in the file. For this assignment, you do not need to worry about this.In these two examples, we use characters 0 and 1 to distinguish between non-leaf and leaf nodes (and 0 to indicate the end of a topology). As there are eight leaf nodes in each of the two examples, there are eight 1's, seven 0's for non-leaf nodes, and another one 0 to indicate that we have reached the end of a topology.To construct a Huffman coding tree from the header information, we make use of a stack. When a 1 is read, we read the corresponding ASCII character and push this character onto the stack. When a 0 is read, there are two possible situations:8Situation 1: if there are more than one element in the stack, we pop the top two elements off the stack and create a new node by combining these two elements. The combination makes the first element off the stack the right child of the new node, and the second element off the stack the left child of the new node. After that, we push the newly created node onto the stack.Situation 2: if the stack contains only one element, we have constructed the entire Huffman coding tree. We pop the entire tree off the stack.Programming AssignmentIn this assignment, you will write a program that takes in a sentence and generates the Huffman tree specified by the header.9