Question

In: Computer Science

IN C++ Given a struct Node { int value; Node *left, *right;}; , implement the functions...

IN C++

Given a struct Node { int value; Node *left, *right;}; , implement the functions below.

a) int getSmallest(Node * r); // return smallest value in the BST with root r. Assume r not null.

b) int getSecondSmallest(Node * r); // return 2nd smallest value in BST with root r. Assume r not null and r has a nonnull left or right child.

c) void removeSecondSmallest(Node * r); // remove 2nd smallest value in BST with root r. Assume r not null and r has a nonnull left or right child.

For part c, if r->value happens to be the second smallest value, then overwrite r->value with some other value in the tree and delete the node containing that value. Don't ever delete r.

Be mindful of efficiency.

code for just the functions. Don't use helper functions.

Solutions

Expert Solution

I have attached the full code of binary search tree and also your fucntions a ,b,and c separately

below code is simple and efficient .


//a
int getSmallest(Node * r)
 {
       Node *temp=r;
       while(temp->left!=NULL)
        {
              temp=temp->left;
        }
        return temp->value;
 }
//b
void getSecondSmallest(Node * r,int &count)
 {
    if (r == NULL || count >= 2) 
        return; 
  
   
    getSecondSmallest(r->left, count); 
  
   
    count++; 
  
    
    if (count == 2) 
    { 
          secondsmall=r->value;
        //cout << "2nd smallest element is "
        //  << r->value<< endl; 
        return; 
    } 
  
    // Recur for left subtree 
   getSecondSmallest(r->right, count);
 }

//c
 Node* removeSecondSmallest(Node * r)
   {
   // get the second smallest value by callig  getSecondSmallest fucntion ()
   // secondsmall stores  the second smallest value
       //if(secondsmall=-1)
          // return root; 
   int key=secondsmall;
     
   Node* curr = r; 
    Node* prev = NULL; 
  
    
    while (curr != NULL && curr->value != key) { 
        prev = curr; 
        if (key < curr->value) 
            curr = curr->left; 
        else
            curr = curr->right; 
    } 
  
    if (curr == NULL) { 
        cout << "Key " << key 
             << " not found in the"
             << " provided BST.\n"; 
        return r; 
    } 
  
    
    if (curr->left == NULL 
        || curr->right == NULL) { 
  
       
        Node* newCurr; 
  
       
        if (curr->left == NULL) 
            newCurr = curr->right; 
        else
            newCurr = curr->left; 
  
       
        if (prev == NULL) 
            return newCurr; 
  
        
        if (curr == prev->left) 
            prev->left = newCurr; 
        else
            prev->right = newCurr; 
  
        
        free(curr); 
    } 
  
    
    else { 
        Node* p = NULL; 
        Node* temp; 
  
       
        temp = curr->right; 
        while (temp->left != NULL) { 
            p = temp; 
            temp = temp->left; 
        } 
  
       
        if (p != NULL) 
            p->left = temp->right; 
  
        else
            curr->right = temp->right; 
  
        curr->value = temp->value; 
        free(temp); 
    } 
    return r; 
 
   }
 

#include<bits/stdc++.h>
using namespace std;
struct Node { 
       int value; 
       Node *left, *right;
       
 };
int secondsmall; 

Node* newNode(int key)
{
        Node* node = new Node;
        node->value = key;
        node->left = node->right = nullptr;

        return node;
} 
Node* insert(Node* root, int key)
{
        
        if (root == nullptr)
                return newNode(key);
  
        if (key < root->value)
                root->left = insert(root->left, key);


        else
                root->right = insert(root->right, key);

        return root;
} 
 
void inorder(Node* root)
{
        if (root == nullptr)
                return;

        inorder(root->left);
        cout << root->value << " ";
        inorder(root->right);
}
int getSmallest(Node * r)
 {
       Node *temp=r;
       while(temp->left!=NULL)
        {
              temp=temp->left;
        }
        return temp->value;
 }
   
 void getSecondSmallest(Node * r,int &count)
 {
    if (r == NULL || count >= 2) 
        return; 
  
   
    getSecondSmallest(r->left, count); 
  
   
    count++; 
  
    
    if (count == 2) 
    { 
          secondsmall=r->value;
        //cout << "2nd smallest element is "
        //  << r->value<< endl; 
        return; 
    } 
  
    // Recur for left subtree 
   getSecondSmallest(r->right, count);
 }
 Node* removeSecondSmallest(Node * r)
   {
   // get the second smallest value by callig  getSecondSmallest fucntion ()
   // secondsmall stores  the second smallest value
       //if(secondsmall=-1)
          // return root; 
   int key=secondsmall;
     
   Node* curr = r; 
    Node* prev = NULL; 
  
    
    while (curr != NULL && curr->value != key) { 
        prev = curr; 
        if (key < curr->value) 
            curr = curr->left; 
        else
            curr = curr->right; 
    } 
  
    if (curr == NULL) { 
        cout << "Key " << key 
             << " not found in the"
             << " provided BST.\n"; 
        return r; 
    } 
  
    
    if (curr->left == NULL 
        || curr->right == NULL) { 
  
       
        Node* newCurr; 
  
       
        if (curr->left == NULL) 
            newCurr = curr->right; 
        else
            newCurr = curr->left; 
  
       
        if (prev == NULL) 
            return newCurr; 
  
        
        if (curr == prev->left) 
            prev->left = newCurr; 
        else
            prev->right = newCurr; 
  
        
        free(curr); 
    } 
  
    
    else { 
        Node* p = NULL; 
        Node* temp; 
  
       
        temp = curr->right; 
        while (temp->left != NULL) { 
            p = temp; 
            temp = temp->left; 
        } 
  
       
        if (p != NULL) 
            p->left = temp->right; 
  
        else
            curr->right = temp->right; 
  
        curr->value = temp->value; 
        free(temp); 
    } 
    return r; 
 
   }
 
 
 
 int main()
 {
      Node* root = nullptr;
        int keys[] = { 15, 10, 20, 18, 12, 16, 5 };

        for (int key : keys)
                root = insert(root, key);
      cout<<" smallest element "<<getSmallest(root)<<endl;
      secondsmall=-1;
      int count=0;
      getSecondSmallest(root,count);
      
      cout<<" second smallest element "<<secondsmall<<endl;
       
      cout<<endl;
      cout<<" -------------------     Inorder Traversal  ------------- "<<endl;
      inorder(root);
      root=removeSecondSmallest(root);
      cout<<endl;
      cout<<" ------------------- After removing second smallest element --- Inorder Traversal  ------------- "<<endl;
      inorder(root);
      
        return 0;
 }

venereology answered 1 year ago
Next > < Previous

Related Solutions

C++ language. struct Node {    int data;    Node *next; } Write a function to...
C++ language. struct Node {    int data;    Node *next; } Write a function to concatenate two linked lists. Given lists A* = (4, 6) and B* = (3, 7, 12), after return from Concatenate_Lists(Node A*, Node B*) the list A should be changed to be A = (4, 6, 3, 7, 12). Your function should not change B and should not directly link nodes from A to B (i.e. the nodes inserted into A should be copies of...
Please show it with python class Node {     int data;     Node left, right;    ...
Please show it with python class Node {     int data;     Node left, right;     public Node(int item)     {         data = item;         left = right = null;     } } public class BinaryTree { // Root of the tree implemented in Node class Node root; Node findLowestCommonAncestor(int node1, int node2) {     return findLowestCommonAncestor(root, node1, node2); } // This function returns pointer to LCA of two given // values node1 and node2. This function assumes that...
Consider the following struct that represents a node within a binary tree: struct Node { int...
Consider the following struct that represents a node within a binary tree: struct Node { int data; // Data of interest Node *left // Link to left subtree (nullptr if none) Node *right ; // Link to right subtree (nullptr if none) }; Complete the following function that computes the number of elements in a binary tree: // Counts the number of elements in the binary tree to which t points. // Returns the number of elements. int size(Node *t)...
Implement stack in C Struct: struct patients{ int id; int severity; char *firstName; char *lastName; char...
Implement stack in C Struct: struct patients{ int id; int severity; char *firstName; char *lastName; char *state; int time_spent; }; Given Array: struct patients* patientsArray[4] = {&p1, &p2, &p3, &p4}; Create two functions one for pushing this array to the stack and one for popping the variables such as p1 p2 p3 p4 by its ID
Please do this code with python. Thank you! struct Node {     int data;     struct...
Please do this code with python. Thank you! 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 {...
Assume that struct Node { int item; Node* link; }; typedef Node* NodePtr; 1. Write function...
Assume that struct Node { int item; Node* link; }; typedef Node* NodePtr; 1. Write function void list_head_insert(NodePtr& head, int entry); The function should insert a new Node, in which entry is the value of attribute item, in front of the linked list that is pointed by head. 2. Write function void list_head_remove(NodePtr& head); The function will remove the first node from the linked list that is pointed by head. 3. Write function NodePtr list_search(NodePtr head, int target); The function...
Please debug the code and answer the questions: #include <stdio.h> typedef struct node { int value;...
Please debug the code and answer the questions: #include <stdio.h> typedef struct node { int value; struct node *next; } node; int ll_has_cycle(node *first) { node * head = first; while (head->next) { head = head->next; if (head == first) return 1; } return 0; } void test_ll_has_cycle(void) { int i,j; node nodes[5]; for(i=0; i < sizeof(nodes)/sizeof(node); i++) { nodes[i].next = NULL; nodes[i].value = i; } nodes[0].next = &nodes[1]; nodes[1].next = &nodes[2]; nodes[2].next = &nodes[1]; printf("Checking first list for cycles....
Assume that struct Node{        int item;        Node* link; }; Write function void list_remove(NodePtr& prev_ptr);...
Assume that struct Node{        int item;        Node* link; }; Write function void list_remove(NodePtr& prev_ptr); The function will remove the node after the node pointed by prev_ptr. c++
C++ tree program (please do NOT use struct Node, use classes) Program 1 Implement a Binary...
C++ tree program (please do NOT use struct Node, use classes) Program 1 Implement a Binary tree using an array Program 2 Implement a tree using linked list - pointer Binary Tree Program 3 - Convert program 1 to a template (include screenshots please of output)
C++ tree program (please do NOT use struct Node, use classes) Program 1 Implement a Binary...
C++ tree program (please do NOT use struct Node, use classes) Program 1 Implement a Binary tree using an array Program 2 Implement a tree using linked list - pointer Binary Tree Program 3 - Convert program 1 to a template
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT