Write a function in C++ to apply left or right rotations to a binary search tree
ID: 3678413 • Letter: W
Question
Write a function in C++ to apply left or right rotations to a binary search tree based on the height of the left and right sub-trees of the root. The function should first determine if a binary search tree is height balanced, and if not, rotate the tree until it is. Your algorithm may need to apply a left or right rotation multiple times. You will not need to apply both a left and right rotation to any tree. The function should return the root of the tree.
TreeNode* CheckHeightAndRotate(TreeNode *root);
The TreeNode Struct is attached as a PDF as well as an expected output. This code is executed on a code runner so only the function above needs to be written.
TreeNode struct: struct TreeNode int key; TreeNode *leftChild; TreeNode rightChild TreeNode *parent Example: Input Tree: 15 18 5 12 Expected Output: 15 3 6 12 18Explanation / Answer
Steps:
Function:
struct TreeNode
{
int key;
TreeNode *leftChild;
TreeNode *rightChild;
TreeNode *parent;
};
int get_height(TreeNode *tree_root)
{
int Left_Height = getHeight(tree_root->leftChild);
int Right_Height = getHeight(tree_root->rightChild);
int H_t= Left_Height - Right_Height;
return Height_Diff;
}
// height
int getHeight(TreeNode *tree_node)
{
if (!tree_node)
{
return 0;
}
return 1 + max(getHeight(tree_node->leftChild), getHeight(tree_node->rightChild));
}
// method to perform left rotation
TreeNode* RL(TreeNode *tree_node)
{
TreeNode *root= tree_node;
TreeNode *Lt = tree_node->rightChild;
tree_node->rightChild = Lt->leftChild;
if(Lt->leftChild != NULL)
{
Lt->leftChild->parent = tree_node;
}
Lt->parent = tree_node->parent;
if (tree_node->parent == NULL)
{
root= Lt;
}
else
{
if(tree_node == tree_node->parent->leftChild)
{
tree_node->parent->leftChild = Lt;
}
else
{
tree_node->parent->rightChild = Lt;
}
}
Lt->leftChild = tree_node;
tree_node->parent = Lt;
return tree_root;
}
TreeNode* RR(TreeNode *tree_node)
{
TreeNode *root= tree_node;
TreeNode *Rt = tree_node->leftChild;
tree_node->leftChild = Rt->rightChild;
if(Rt->rightChild != NULL)
{
Rt->rightChild->parent = tree_node;
}
Rt->parent = tree_node->parent;
if(tree_node->parent == NULL)
{
root= Rt;
}
else if(tree_node == (tree_node->parent->leftChild))
{
tree_node->parent->leftChild = Rt;
}
else
{
tree_node->parent->rightChild = Rt;
}
Rt->rightChild = tree_node;
tree_node->parent = Rt;
return tree_root;
}
//method to check the height and then rotate
TreeNode* CheckHeightAndRotate(TreeNode *root)
{
TreeNode *Bal;
int H_t= get_height(root);
//now after getting the height the rotation process is //performed
while(H_t> 0)
{
Bal = RR(root);
root = Bal;
H_t= get_height(root);
}
while(H_t< 0)
{//call left rotation
Bal = RL(root);
root = Bal;
H_t= get_height(root);
}
return Bal;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.