Write a program in C++. Please provide three files separately

1. Header file (.h)

2. Implementation file(.cpp)

3. Driver Program Problem:

An a-b tree is a binary tree in which each node can contain either one key or two keys. The children in a node's left subtree are all less than or equal to the largest key at the node. In the following example, the keys are all single characters: The root node contains 2 keys, d and g. It has a left child that contains a single node, c. The right child is a node with 2 keys, s and v. That node has two chidren, the left child has keys u and m the right child, the key w. Inserting into an a-b tree is like inserting into a binary search tree, except when you come to a node containing only one key, you simply add the new key to the node containing one key. The node then contains two keys. For example, b would be added to the node containing c. More interestingly, consider what happens when an f is added to the tree. At the root, we go left (since t is less than or equal to the larger of the keys at the root), and then to the right of eb (since f is larger than the larger of the keys in the node). And so on. Input: Five strings. Each string will be less than 50 characters long and will contains the letters A through Z. Each letter is a key to be added to an initially empty a-b tree. Output: For each input string, print the tree using in in-order. That is, print a node's left subtree then the node, and then the node's right subtree. Within a node with 2 keys, the keys are liste in the order in which they were added to the node. The in-order listing of the tree above (after 1 and f are added) is: cbfdgusv w. Sample Input: Line #1: INDIA Line #2: CANADA Line #3: PORTUGAL Line #4: SWITZERLAND Line #5: UNITEDKINGDOM Sample Output: Output #1: A D 1 1 N Output #2: A A C A N D Output #3: G ALPORTU Output #4: D L A N E R 1 Tswz Output #5: D E D G K 1 HNOITUN