10 Mar This is the only file given I read the instructions and he gave two files main.cc and tree.h but they are both empty so I have to

Purpose: To teach you BSTs and have you implement them from scratch in a greenfield assignment. Then to visualize them in BRIDGES, which is neat. This program is basically a puzzle solver for a class of puzzles like the one used in my published Dungeons and Dragons game, A Tale of Two Towers. Directions: This project has three phases: 1) Inputting the layout of a dungeon 2) Solving the dungeon (5 points) 3) Visualizing the dungeon using BRIDGES (5 points) Input Phase: The dungeon is made up of rooms. Each room has a letter engraved on the ground, a button to push, and two doors leading from it to the left (southwest) and right (southeast). The dungeon has an interesting property that the letter on the ground of every room is lower to the left (southwest) and higher to the right (southeast). This means you can represent the dungeon as a binary search tree (BST). The input takes the form of a series of letters, followed by a number to indicate the end of input (the number is not added to the dungeon). Each letter is inserted into the dungeon in order, with one room created per letter. Example input: BDCAF6 This would create a dungeon that looks like this: B / A D / C F Solving Phase: The user will then type in a password, a string of characters. The end of input is designated by hitting ctrl-d, which sends the EOF character to the input. So you'll read one char at a time, and if you get an EOF (i.e. "if (x == EOF)" ) you are done with the input. First, you must check to see if the maze is solvable. For example, if the password for the dungeon above was "ABCDZZZ", this would not be solvable, since there is no room Z in the maze. If this is the case, print "NOT SOLVABLEn" to the screen. If the maze is solvable, then you must print directions on how to solve the maze. The player will start at the root of the tree. For each char that your read, you must print directions on how to solve the maze. If you ever reach the spot where that letter is found, print: "Found LETTER. Retrace your steps to the entrance.n" (Where LETTER is the letter you were searching for.) If the room you are looking for is to the left, print: "Take the left door at the LETTER.n" and then recursively repeat the algorithm to the left. (LETTER is the letter on the ground in that room) If the room you are looking for is to the right, print: "Take the right door at the LETTER.n" and then recursively repeat the algorithm to the left. After you have printed directions to all of the letters in the password, print: "Exit the dungeon!n"; And quit. ====== FUN PHASE ====== Next you get to visualize your dungeon on BRIDGES!!! To do so, you need to learn two very important programmer skills: 1) How to read documentation, and 2) How to steal liberally from sample source code and adapt it to your needs This web page has everything you need to solve this assignment – https://bridgesuncc.github.io/tutorials/BinarySearchTree.html —–~/dungeon_delve 5 points correctness, 5 points visualizing it in BRIDGES. Upload a link to your BRIDGES visualization.