Project 1: Balanced Tree

C++ Program: You will turn a plain binary search tree into a red-black tree.

Start with the following code for a binary search tree (from Data Structures and Algorithms): Project 1 (Balanced Tree).zip Download Project 1 (Balanced Tree).zip. Then, make the following modifications:

• Add a field for the parent of a node.
• Rewrite the code to add a value to the tree, such that it always also stores the parent in a node.
• Add a field for the color of a node.
• Create a static node to represent the Nil object and use it in place of the NULL pointer throughout the tree code where appropriate.
• Rewrite the code that adds a value to the tree, applying the red-black tree algorithms, i.e., coloring and rotating as needed to maintain balance.

Bonus: Add member function(s) to display the binary search tree in breadth-first order, 1 level per line, using a queue (see https://www.geeksforgeeks.org/level-order-traversal-line-line-set-3-using-one-queue/ Links to an external site.).

This will  help you to validate that the red-black tree is constructed properly. For example, the original binary search tree produces the following levels for 10 products when showing the last 2 digits of the product id (doesn't indicate parent at preceding level):

00
58
45 91
36 53 94
16
12 26

Pass a function to allow displaying the values in the tree as desired, much like how the existing traverse() member function works. You may wish to display node color as part of the output.