Write a function to apply left or right rotations to a binary search tree based
ID: 3817028 • 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.
USE ONLY THIS FUNCTION HEADER:
TreeNode* CheckHeightAndRotate(TreeNode *root);
TreeNode struct:
Example:
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
#define bool int
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct treenode
{
int data;
struct treenode* left;
struct treenode* right;
};
/* Returns the height of a binary tree */
int height(struct treenode* node);
/* Returns true if binary tree with root as root is height-balanced */
bool isBalanced(struct treenode *root)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */
/* If tree is empty then return true */
if(root == NULL)
return 1;
/* Get the height of left and right sub trees */
lh = height(root->left);
rh = height(root->right);
if( abs(lh-rh) <= 1 &&
isBalanced(root->left) &&
isBalanced(root->right))
return 1;
/* If we reach here then tree is not height-balanced */
return 0;
}
/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */
/* returns maximum of two integers */
int max(int a, int b)
{
return (a >= b)? a: b;
}
/* The function Compute the "height" of a tree. Height is the
number of nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct node* node)
{
/* base case tree is empty */
if(node == NULL)
return 0;
/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + max(height(node->left), height(node->right));
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->left->left = newNode(8);
if(isBalanced(root))
printf("Tree is balanced");
else
printf("Tree is not balanced");
getchar();
return 0;
}.
.
.there is another method of logic. To implemt the same binary tree logic
#include<stdio.h>
#include<stdlib.h>
#define bool int
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct treenode
{
int data;
struct treenode* left;
struct treenode* right;
Struct treenode*parent;
};
/* The function returns true if root is balanced else false
The second parameter is to store the height of tree.
Initially, we need to pass a pointer to a location with value
as 0. We can also write a wrapper over this function */
bool isBalanced(struct treenode *root, int* height)
{
/* lh --> Height of left subtree
rh --> Height of right subtree */
int lh = 0, rh = 0;
/* l will be true if left subtree is balanced
and r will be true if right subtree is balanced */
int l = 0, r = 0;
if(root == NULL)
{
*height = 0;
return 1;
}
/* Get the heights of left and right subtrees in lh and rh
And store the returned values in l and r */
l = isBalanced(root->left, &lh);
r = isBalanced(root->right,&rh);
/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = (lh > rh? lh: rh) + 1;
/* If difference between heights of left and right
subtrees is more than 2 then this node is not balanced
so return 0 */
if((lh - rh >= 2) || (rh - lh >= 2))
return 0;
/* If this node is balanced and left and right subtrees
are balanced then return true */
else return l&&r;
}
/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main()
{
int height = 0;
/* Constructed binary tree is
1
/
2 3
/ /
4 5 6
/
7
*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->left->left->left = newNode(7);
if(isBalanced(root, &height))
printf("Tree is balanced");
else
printf("Tree is not balanced");
getchar();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.