Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Only the methods rotateLeft, rotateRight, and rotateRightLeft can be changed. But here is the full code to put in for troubleshooting: #include #include class Node
Only the methods "rotateLeft", "rotateRight", and "rotateRightLeft" can be changed.
But here is the full code to put in for troubleshooting:
#include#include class Node { public: int name; Node* left = NULL; Node* right = NULL; }; Node* insert(Node* root, int key) { if(root==NULL) { Node* temp=new Node(); temp->name=key; return temp; } if (key name) root->left = insert(root->left, key); else if (key > root->name) root->right = insert(root->right, key); return root; } std::string traverse(Node* head) { std::string string1, string2, string3; if (head == NULL) return ""; string1 = traverse(head->left); string2 = std::to_string(head->name); string3 = traverse(head->right); return string1+" "+string2+" "+string3; } int height(Node* head) { if (head == NULL) return -1; if ((head->left == NULL) && (head->right == NULL)) return 0; int heightLeft = 0; int heightRight = 0; if (head->left != NULL) heightLeft = height(head->left); if (head->right != NULL) heightRight = height(head->right); if (heightLeft>heightRight) return 1+heightLeft; else return 1+heightRight; } Node* rotateLeft(Node *node) { if(node->right != NULL) { struct Node *alpha = node->right; struct Node *beta = alpha->left; alpha->left = node; node->right = beta; } } Node* rotateRight(Node *node) { if(node->left != NULL) { struct Node *alpha = node->left; struct Node *beta = alpha->right; alpha->right = node; node->left = beta; } } Node* rotateRightLeft(Node *node) { rotateRight(node); rotateLeft(node); } int main() { Node* root=NULL; int x; int num; std::cin >> num; for(int i=0;i >x; root=insert(root,x); } root=rotateRightLeft(root); std::cout Write three functions Node* rotateLeft (Node *node) Node* rotateRight (Node node); Node rotateRightLeft(Node *node); These functions will take a node at which point you should perform the respective rotations for the balanced tree and return the new root. The left right rotation should be performed as a left rotation on node's left child, then a right rotation on node The first input in test cases is the number of nodes. The second input is nodes of a tree which are inserted into a binary search tree that order You don't need to implement insert. You have access to the root of the constructed Binary Search Tree We will create the tree for you, then call rotateLeftRight on the root of the tree. We will call in-order traversal to check your output and height. You do not need to implement the in-order traversal or the height. The output is an in-order traversal of the tree after the rotation and the height of the final tree. My code Node* rotateLeft (Node node) if (node-right ! struct Node talphanode->right struct Node *beta alpha->left; alpha-left node node->right beta; Sample Input 1 Node* rotateRight (Node *node) 10 20 15 if(node->left != 1) { Sample Output 1 struct Node alpha node->left struct Node *beta -alpha-right alpha-right node; node->left = beta; 18 15 20 Sample Input 2: 18 5 20 15 16 21 Sample Output 2 Node rotateRightLeft (Node *node) 5 10 15 16 20 21 rotateRight (node) rotateLeft (node My outputs: 6 10 5 20 15 16 21 10 20 15 10 15 10 15 16 2 Process finished with exit code 0 Process finished with exit code 0
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started