Double Threaded BST

Implement a Double-Threaded Binary Tree and add in-order and reverse-order printing without resorting to recursion Project 5.2 in the text see image.

Using the following supplied C++ files implement a right and left threaded binary search tree (see https://algorithms.tutorialhorizon.com/double-threaded-binary-tree-complete-implementation/ for more information on doubly threaded BSTs). The files provided to you come from our text, with some minor modifications, and implement a BST based dictionary. You must modify this BST-based dictionary to implement a threaded BST. Specifically, you will need to make the following modifications:

BSTNode.h

• Add Boolean instance variables to indicate whether a node pointer is a thread or regular pointer. You may not add any additional pointers to BSTNode. The whole idea of threads is that they take advantage of unused BSTNode pointers and thereby reduce the binary tree's wasted overhead.
• Add setter/getter methods to access the Boolean instance variables or modify existing setters/getters as necessary.

BST.h

• Rewrite method inserthelp() to take advantage of the modified BSTNode in which a pointer can be either a regular pointer or a thread.
• Modify method printhelp() to work with threaded nodes.
• Add method printInorder() to do an inorder printing of your tree without the use of recursion.
• Add printReverse() to do a reverse order printing of your tree without resorting to recursion.
• You may add private helper methods as needed to make modifying or creating the methods above easier.
• Note: I've commented out the destructor since the destructor relies on clearhelp() and clearhelp(), as currently written, wont work with threaded trees.
• Note: You do not have to implement any of the functions I've removed or deleted. Only the functions Ive specified above, along with any private helper functions you need, must be implemented.

Approach - in a Word document explain your implementation approach. Tell me how you plan to accomplish this assignment. Tell me where in your source files (source file names and method/function names) I can look to see your implementation. Use methods printhelp, printInorder, and printReverse to demonstrate your program in action. Include screen shots of your program's output.

Since the BST node takes a key value pair I want you to insert the following values (in the order provided) to build your tree.

77, "seventy-seven"
70, "seventy"
75, "seventy-five"
66, "sixty-six"
79, "seventy-nine"
68, "sixty-eight"
67, "sixty-seven"
69, "sixty-nine"
90, "ninety"
85, "eighty-five"
83, "eighty-three"
87, "eighty-seven"
65, “sixty-five”

Files provided:

• BST.h
• BSTNode.h
• BinNode.h
• dictionary.h

Here is an example of my test run showing both printhelp, printInorder, and printReverse: see image.