The assignment is in the file

The assignment is in the file


SP23_COSC3333_HW3 COSC 3333 - Data Structures & Algorithms II Spring 2023 Programming Assignment 3 Due Date: Saturday, April 15 @ 11:59 p.m. Download the code provided by the textbook in order to complete this program. Please note that no Java classes for specific data structures or associated algorithms can be used for any assignments for this course, except the one in Tree class that is used in displayTree method. You MUST follow the outlined instructions to secure the full credit. No credit will be given to programs that just generate the output but do not follow the methodology given. The assignment is based on a complete or nearly complete Binary Tree, where each node carries a numeric label, as well as a random uppercase alphabetical letter. The user gets to choose the size of this Binary Tree in the range 5-20 inclusive. You will build it by numbering each node sequentially, and populating its character attribute by a random uppercase alphabetical letter. The following gives an example of a 15-node and a 9-node BT: ................................................................................................................................. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ................................................................................................................................. ................................................................................................................................. 1 2 3 4 5 6 7 8 9 -- -- -- -- -- -- ................................................................................................................................. As you can see, these nodes are sequentially numbered and are positioned based on their numeric labels. So for the first step of the assignment build this Binary Tree. Notice this BT will NOT be built based on the letter attributes of the nodes. This must be a complete or nearly complete Binary Tree whose nodes’ numeric labels are based on the position of the node on each level of the Binary Tree. How do you think you can build such tree? Whatever data structure or methodology you used to build your Binary Tree, after completion of it, you are only going to refer to this Binary Tree for the rest of the operations for this assignment and not the structure(s) you used to build it. It is of utmost importance that your code adheres to these specifications. One task of this assignment involves the user choosing nodes only based on their numeric labels and see if that combination results in any meaningful word which will be composed of each node’s letter attribute. Notice we will not be able to use any AI for that determination, it will be for the user to judge the resultant word! The user can choose nodes as many times as they wish. However, they must first determine how many letters/nodes they will be choosing. Next they refer to the numeric labels of the nodes, where you need to look each node up based on their positioning numeric label, and display their letter attribute one next to another to form a word. You may also choose to append these letters to form as string. As you already know, Binary Trees are not Search Trees, so even if we know the numeric label of a node, we still need to check every node or do some arithmetic to get to that node, every time the user selects a node. In the textbook, we covered a strategy in finding the last node in a Tree-based Heap. Here we are going to use that technique along with the hashing scheme of direct addressing to facilitate the search for any given node based on their position in the tree i.e. their numeric label. The hashing scheme hashes each node based on their label to the matching hash index. Node #3 hashes to index 3 in the hash table. Notice that the reasonable size of our Binary Tree makes it possible for us to use direct addressing. But since these nodes are id’ed by their numeric labels and not any other attributes, we need to store the path to get to them, in their hash index and not say their letter attribute. What size do you choose for the hash table? So in summary: