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.

Hint: You can use a helper function for calculating height.

GIVEN h file

#pragma once

#include

// Definition for a binary tree node. struct TreeNode { int val_; int balance_; TreeNode *left_; TreeNode *right_; TreeNode(int x) { left_ = NULL; right_ = NULL; val_ = x; balance_ = 0; } };

TreeNode* findLastUnbalanced(TreeNode* root);

void deleteTree(TreeNode* root);