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 <stdbool.h>
2#include <stdio.h>
3#include <stdlib.h>
4
5struct TreeNode {
6 int val;
7 struct TreeNode *left;
8 struct TreeNode *right;
9};
10
11int height(struct TreeNode* node) {
12 if (node == NULL) return 0;
13 int leftHeight = height(node->left);
14 int rightHeight = height(node->right);
15 return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
16}
17
18bool isBalanced(struct TreeNode* root) {
19 if (root == NULL) return true;
20 int leftHeight = height(root->left);
21 int rightHeight = height(root->right);
22 return abs(leftHeight - rightHeight) <= 1 && isBalanced(root->left) && isBalanced(root->right);
23}In this C implementation, a recursive function height is used to determine the height of each node's left and right subtree. For each node, we verify if the difference in height is more than 1. The solution exploits recursion to calculate tree height in a bottom-up manner.
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#include <iostream>
2#include <cmath>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool isBalanced(TreeNode* root) {
return checkBalance(root).second;
}
private:
pair<int, bool> checkBalance(TreeNode* node) {
if (!node) return {0, true};
auto left = checkBalance(node->left);
if (!left.second) return {0, false};
auto right = checkBalance(node->right);
if (!right.second) return {0, false};
bool balanced = abs(left.first - right.first) <= 1;
return {fmax(left.first, right.first) + 1, balanced};
}
};In this optimized C++ solution, we use std::pair to return both the tree height and its balanced status from the helper checkBalance function. The algorithm stops calculating further heights as soon as an imbalance is found.