Sponsored
Sponsored
This approach involves recursively calculating the height of each subtree and checking if the subtrees are balanced by ensuring the difference in height is not more than one.
Time Complexity: O(N^2), where N is the number of nodes in the tree, as we recalculate the height of subtrees multiple times. Space Complexity: O(N) due to recursion stack.
1#include <iostream>
2#include <cmath>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10};
11
12int height(TreeNode* node) {
13 if (!node) return 0;
14 return max(height(node->left), height(node->right)) + 1;
15}
16
17bool isBalanced(TreeNode* root) {
18 if (!root) return true;
19 int leftHeight = height(root->left);
20 int rightHeight = height(root->right);
21 if (abs(leftHeight - rightHeight) > 1) return false;
22 return isBalanced(root->left) && isBalanced(root->right);
23}This C++ solution follows a similar approach to the C implementation. We define a helper method, height, which evaluates the height of the binary tree recursively. At each step, we ensure that every subtree is balanced by checking the height difference criterion.
This optimized approach calculates the height and balance status of a tree in a single recursive function, thus avoiding recalculations by returning both height and balanced status in form of tuples or objects.
Time Complexity: O(N). Space Complexity: O(N), which includes the recursion stack depth.
1#
We use a helper struct Result holding both height and balanced state. The checkBalance function recurses over nodes, aggregating this data, and halting early if imbalance is detected.