Write a function to apply left or right rotations to a binary search tree based
ID: 3817521 • Letter: W
Question
Write a function 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.
some test cases:
Write a function 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. Tree Node CheckHeightAndRotate(TreeNode *root); TreeNode struct: struct TreeNode int key; TreeNode *left Child; TreeNode right child TreeNode parent; Example: Input Tree 15 18 5 12 3 6 Expected output: 15 3 6 12 18Explanation / Answer
struct Treenode
{
int key;
int height;
struct Treenode * leftchild;
struct Treenode * rightchild
};
Treenode * CheckHeightAndRotate(Treenode * root)
{CheckHeight(root);
if(height(root->leftchild) - height(root->rightchild) == 2)
{
if(height(root->leftchild->rightchild) > height(root->leftchild->leftchild))
root->leftchild=rotate_left(root->leftchild);
return rotate_right(root);
}
else if(height(root->rightchild)-height(root->leftchild) ==2)
{
if(height(root->rightchild->leftchild)>height(root->rightchild->rightchild))
root->rightchild=rotate_right(root->rightchild)
return rotate_left(root);
}
return root;
}
void CheckHeight(Treenode * root)
{
root->height=1+max(height(root->leftchild),height(root->rightchild);
}
Treenode * rotate_right(Treenode * p)
{
Treenode * q=p->leftchild;
p->leftchild=q->rightchild;
q->rightchild=p;
CheckHeight(p);
CheckHeight(q);
return q;
}
Treenode * rotate_left(Treenode *p)
{
Treenode * q=p->rightchild;
p->rightchild=q->leftchild;
q->leftchild=p;
CheckHeight(p);
CheckHeight(q);
return q;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.