Question

part C please

8 BST 15 Points Given a BST T with root r write algorithms (pseudocode) to determine: (a) The height of T. (b) The maximum element in T. (c) If T is height balanced. Please select file(s) Select file(s) Q9 Double

Answer 1

`Hey,

Note: If you have any queries related to the answer please do comment. I would be very happy to resolve all your queries.

BELOW IS THE ALGO IN PSEUDOCODE

int isHeightBalanced(Node* root, bool& isBalanced)
{
// base case: tree is empty or tree is not balanced
if (root == nullptr || !isBalanced)
return 0;

// get height of left subtree
int left_height = isHeightBalanced(root->left, isBalanced);

// get height of right subtree
int right_height = isHeightBalanced(root->right, isBalanced);

// tree is unbalanced if absolute difference between height of
// its left subtree and right subtree is more than 1
if (abs(left_height - right_height) > 1)
isBalanced = false;

// return height of subtree rooted at current node
return max(left_height, right_height) + 1;
}

// Main function to check if given binary tree is height balanced or not
bool isHeightBalanced(Node* root)
{
bool isBalanced = true;
isHeightBalanced(root, isBalanced);

return isBalanced;
}

CALL THE FUNCTION AS

isHeightBalanced(T)

Kindly revert for any queries

Thanks.