Threaded BST

Description:

Threaded Binary Search Tree (single thread; right): the program replicates a binary search tree however the BST is now threaded. Adding threading allows to traverse the nodes in order by using the threads for every node; thus, traversing without recursion or the use of a stack. Therefore, limiting the amount of space required to keep track of nodes. Uses Catch Framework for creation of test cases.

Commands within bstt.h class:

• copy constructor / destructor present. [O(N)]
• operator=: clears "this" tree and then makes a copy of the "other" tree. [O(N)]
• clear: clears the tree's nodes and all its contents that were from the struct (tree is now empty). [O(N)]
• size: returns the number of nodes in the tree. [O(1)]
• search: searches for the key in the tree and returns boolean value accordingly. [O(lgN)]
• search2: searches for the key to the right of the requested key and returns boolean value. [O(lgN)]
• insert: inserts user's node as (key, value) pair. [O(lgN)]
• operator[]: returns the value that the user requests and if not found then return default value. [O(lgN)]
• operator(): finds the key and returns the key to the right. If threaded then follow thread to next key inorder. Not found will result in default value.
• begin: obtains the first key to initiate inorder traversal [O(lgN)]
• next: follows the thread and returns key that is next inorder by pass by reference.
• dump: output tree's contents.

Data Structure: Binary Search Tree
Leveraged Knowledge: use of map and deque data structures, the idea of scopes within a program by the use of a stack by the use of the compiler, Catch Framework.

Download Code Here