In order to balance a tree, we have to first find nodes about which rotations ha

Question

In order to balance a tree, we have to first find nodes about which rotations have to be made. In this question, complete the findLastUnbalanced function that accepts a TreeNode * root and finds the deepest node that is unbalanced. Remember that an unbalanced node has subtrees of heights differing by more than 1.

Note: If there are multiple unbalanced nodes, you have to return the one farthest from the root. If there are no unbalanaced nodes, return NULL.

#incLude #incLude "TreeNode . h" ! 2 4 using namespace std; 6 TreeNodex findLastUnbalanced (TreeNode* root) 7 8 10 void deleteTree(TreeNode* root) if (root= NULL) return; 12 13 deleteTree (root->left_); 14 deleteTree (root->right_); 15 16 17 18 delete root; root = NULL;

Explanation / Answer

void findLastUnbalancedUtil(TreeNode *root,int *distance,int height, TreeNode **unbalanceNode)

{

if(root==NULL) return;

if(root->balance_>1 || root->balance_<-1)

{

if((*distance)<height)

{

(*distance)=height;

(*unbalanceNode)=root;

}

}

findLastUnbalancedUtil(root->left_,distance,height+1);

findLastUnbalancedUtil(root->right_,distance,height+1);

}

TreeNode *findLastUnbalanced(TreeNode*root)

{

if(root==NULL) return NULL;

int height=1,distance=0;

TreeNode *unbalancedNode=NULL;

findLastUnbalancedUtil(root,&distance,height,&unbalancedNode);

return unbalancedNode;

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.