Question

In: Computer Science

Question - 1 Using the structural node and methods discussed in Binary Search Tree lectures, create...

Question - 1
Using the structural node and methods discussed in Binary Search Tree lectures, create a method for the Binary Search Tree that takes an unsorted input list and constructs a Binary Search Tree based on its values. Any duplicate value will only appear once on the tree. This method outputs a Binary Search Tree structure (not an enumeration of the tree). Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify its purpose.

Illustrate the performance of method enumerating the tree using level-order-traversal method on 3 examples of sizes (10, 20 and 30) and on the data below.

datalist= [199, 666, 930, 751, 120, 411, 534, 716, 134, 379, 908, 97, 740, 904, 575, 437, 983, 835, 931, 768, 405, 544, 553, 821, 160, 312, 228, 324, 675, 622, 768, 312, 310, 18, 558, 170, 842, 214, 545, 857, 6, 71, 421, 909, 908, 377, 488, 837, 884, 382, 1, 654, 207, 751, 459, 450, 431, 462, 40, 926, 304, 594, 966, 386, 760, 39, 297, 557, 125, 327, 278, 328, 937, 195, 346, 419, 953, 681, 203, 173, 807, 710, 428, 415, 601, 258, 981, 464, 568, 546, 308, 883, 431, 948, 529, 55, 651, 73, 411, 719, 172, 43, 249, 695, 636, 603, 447, 652, 211, 736, 923, 27, 198, 427, 154, 572, 671, 314, 25, 428, 900, 930, 378, 806, 281, 805, 627, 748, 23, 961, 244, 587, 352, 939, 880, 69, 52, 702, 856, 990, 19, 743, 132, 793, 279, 500, 776, 921, 583, 487, 638, 753, 209, 870, 506, 995, 691, 743, 501, 831, 549, 369, 718, 780, 17, 636, 217, 486, 548, 500, 381, 116, 84, 683, 908, 151, 633, 404, 4, 426, 92, 614, 851, 714, 90, 789, 441, 985, 539, 470, 891, 384, 962, 259, 938, 211, 683, 560, 630, 893, 106, 841, 974, 114, 239, 896, 796, 524, 896, 974, 583, 729, 577, 863, 696, 530, 670, 467, 841, 401, 209, 596, 862, 702, 21, 219, 902, 271, 293, 350, 357, 182, 179, 909, 874, 769, 192, 39, 7, 487, 571, 155, 565, 231, 36, 544, 443, 24, 596, 570, 129, 585, 529, 557, 833, 270, 241, 732, 569, 839, 762, 881, 177, 149, 413, 806, 545, 591, 721, 289, 453, 53, 470, 215, 480, 218, 787, 915, 532, 626, 18, 349, 216, 338, 572, 979, 939, 76, 55, 49, 727, 524, 68, 403, 941, 234, 85, 991, 698, 561]

Solutions

Expert Solution

// C++ Program of above implementation 
#include <iostream> 
using namespace std; 
  
// Struct declaration 
struct Node { 
    int data; 
    struct Node* left; 
    struct Node* right; 
}; 
  
// Node creation 
struct Node* newNode(int data) 
{ 
    struct Node* nn 
        = new Node; 
    nn->data = data; 
    nn->left = NULL; 
    nn->right = NULL; 
    return nn; 
} 
  
// Function to insert data in BST 
struct Node* insert(struct Node* root, int data) 
{ 
    if (root == NULL) 
        return newNode(data); 
    else { 
        if (data < root->data) 
            root->left = insert(root->left, data); 
        if (data > root->data) 
            root->right = insert(root->right, data); 
        return root; 
    } 
} 
  
// InOrder function to display value of array 
// in sorted order 
void inOrder(struct Node* root) 
{ 
    if (root == NULL) 
        return; 
    else { 
        inOrder(root->left); 
        cout << root->data << " "; 
        inOrder(root->right); 
    } 
} 
  
// Driver code 
int main() 
{ 
    int arr[] = { 199, 666, 930, 751, 120, 411, 534, 716, 134, 379, 908, 97, 740, 904, 575, 437, 983, 835, 931, 768, 405, 544, 553, 821, 160, 312, 228, 324, 675, 622, 768, 312, 310, 18, 558, 170, 842, 214, 545, 857, 6, 71, 421, 909, 908, 377, 488, 837, 884, 382, 1, 654, 207, 751, 459, 450, 431, 462, 40, 926, 304, 594, 966, 386, 760, 39, 297, 557, 125, 327, 278, 328, 937, 195, 346, 419, 953, 681, 203, 173, 807, 710, 428, 415, 601, 258, 981, 464, 568, 546, 308, 883, 431, 948, 529, 55, 651, 73, 411, 719, 172, 43, 249, 695, 636, 603, 447, 652, 211, 736, 923, 27, 198, 427, 154, 572, 671, 314, 25, 428, 900, 930, 378, 806, 281, 805, 627, 748, 23, 961, 244, 587, 352, 939, 880, 69, 52, 702, 856, 990, 19, 743, 132, 793, 279, 500, 776, 921, 583, 487, 638, 753, 209, 870, 506, 995, 691, 743, 501, 831, 549, 369, 718, 780, 17, 636, 217, 486, 548, 500, 381, 116, 84, 683, 908, 151, 633, 404, 4, 426, 92, 614, 851, 714, 90, 789, 441, 985, 539, 470, 891, 384, 962, 259, 938, 211, 683, 560, 630, 893, 106, 841, 974, 114, 239, 896, 796, 524, 896, 974, 583, 729, 577, 863, 696, 530, 670, 467, 841, 401, 209, 596, 862, 702, 21, 219, 902, 271, 293, 350, 357, 182, 179, 909, 874, 769, 192, 39, 7, 487, 571, 155, 565, 231, 36, 544, 443, 24, 596, 570, 129, 585, 529, 557, 833, 270, 241, 732, 569, 839, 762, 881, 177, 149, 413, 806, 545, 591, 721, 289, 453, 53, 470, 215, 480, 218, 787, 915, 532, 626, 18, 349, 216, 338, 572, 979, 939, 76, 55, 49, 727, 524, 68, 403, 941, 234, 85, 991, 698, 561 }; 
  
    // Finding size of array arr[] 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    struct Node* root = NULL; 
  
    for (int i = 0; i < n; i++) { 
  
        // Insert element of arr[] in BST 
        root = insert(root, arr[i]); 
    } 
  
    // Inorder Traversal to print nodes of Tree 
    inOrder(root); 
    return 0; 
} 

Related Solutions

PYTHON CODING Using the structural node and methods discussed in Binary Search Tree below # Binary...
PYTHON CODING Using the structural node and methods discussed in Binary Search Tree below # Binary Tree Node structure class Node: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None class BSTree(): def __init__(self, rootdata): self.root = Node(rootdata)    def insert(self, data, cur_node): if data < cur_node.data: if cur_node.left == None: cur_node.left = Node(data) else: self.insert(data, cur_node.left)    elif data > cur_node.data: if cur_node.right == None: cur_node.right = Node(data) else:...
Question 3: Create a method for the Binary Search Tree (deleteNode) that deletes a specified node...
Question 3: Create a method for the Binary Search Tree (deleteNode) that deletes a specified node identified by its value, and rearranges the descendants of the deleted node to ensure the resulting Tree meets the requirements of a Binary Search Tree. a) Discuss and justify your approach to address each possible case. b) Is the new tree (with the deleted node removed) unique? Discuss your answer. Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or...
In java, create a binary search tree (without using additional libraries) of stacks where each node...
In java, create a binary search tree (without using additional libraries) of stacks where each node contains a key and a stack. In this binary search tree, when adding a new element to the tree it is inserted based off of its key value; if that key value already exist then the element is pushed into the stack at that location, if the key value does not exist a node element is added to the tree to reflect that key,...
Implement a function to find a node in a binary search tree. Using the following class...
Implement a function to find a node in a binary search tree. Using the following class and function definition. If a node with a matching value is found, return a pointer to it. If no match is found, return nullptr. #include <iostream> class BTNode { public: int item; BTNode *left; BTNode *right; BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){} }; BTNode *root = nullptr; BTNode *find(int item) { //implement code here return nullptr; } int main() {    root = new...
Create a binary search tree of stacks where each node contains a key and a stack.
IN C++   Create a binary search tree of stacks where each node contains a key and a stack. In this binary search tree, when adding a new element to the tree it is inserted based off of its key value; if that key value already exist then the element is pushed into the stack at that location, if the key value does not exist a node element is added to the tree to reflect that key, and a empty...
PYTHON CODING Create a method for the Binary Search Tree (deleteNode) that deletes a specified node...
PYTHON CODING Create a method for the Binary Search Tree (deleteNode) that deletes a specified node identified by its value, and rearranges the descendants of the deleted node to ensure the resulting Tree meets the requirements of a Binary Search Tree. a) Discuss and justify your approach to address each possible case. b) Is the new tree (with the deleted node removed) unique? Discuss your answer. Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or...
PYTHON CODING Create a method for the Binary Search Tree (deleteNode) that deletes a specified node...
PYTHON CODING Create a method for the Binary Search Tree (deleteNode) that deletes a specified node identified by its value, and rearranges the descendants of the deleted node to ensure the resulting Tree meets the requirements of a Binary Search Tree. a) Discuss and justify your approach to address each possible case. b) Is the new tree (with the deleted node removed) unique? Discuss your answer. Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or...
Binary Tree Create a binary search tree using the given numbers in the order they’re presented....
Binary Tree Create a binary search tree using the given numbers in the order they’re presented. State if the resulting tree is FULL and/or BALANCED. 37, 20, 18, 56, 40, 42, 12, 5, 6, 77, 20, 54
Implement a function to remove a leaf node from a binary search tree. Using the following...
Implement a function to remove a leaf node from a binary search tree. Using the following class and function definition: class BTNode { public: int item; BTNode *left; BTNode *right; BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){} }; BTNode *root = nullptr; BTNode * remove_leaf(int item, bool &removed) { // implement } The remove function will return the node with the item if it's present in the tree. If the node is a leaf node and is removed by the function,...
1. Draw a binary search tree as a single root node holding a string as the...
1. Draw a binary search tree as a single root node holding a string as the data element. Each string inserted into a node in the tree will be for a character in a game. Then, draw a new tree each time you insert a new node into the tree holding a string Insert 4 nodes total, including the root. This means the new nodes will need to be inserted at the correct child to maintain the BST property.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT