# Solution For Balanced Binary Tree

The Balanced Binary Tree problem on LeetCode can be found at https://leetcode.com/problems/balanced-binary-tree/.

The problem statement is as follows:
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

To solve this problem, we need to recursively check the height of the left and right subtrees of each node and compare them. If the difference between the heights is greater than 1, then the tree is not height-balanced.

We will implement a recursive solution to check the height of the tree and compare the heights of the left and right subtrees.

First, we will define a helper function to calculate the height of a given node:
`int height(TreeNode* node) { if (!node) { return 0; } return 1 + max(height(node->left), height(node->right)); }`

The `height` function takes a node as input and recursively calculates the height of the subtree rooted at that node. If the node is `NULL`, the function returns 0. Otherwise, it returns 1 plus the maximum height of the left and right subtrees.

Next, we will define the main function `isBalanced` which takes the root of the binary tree as input:
`bool isBalanced(TreeNode* root) { if (!root) { return true; } int leftHeight = height(root->left); int rightHeight = height(root->right); if (abs(leftHeight - rightHeight) > 1) { return false; } return isBalanced(root->left) && isBalanced(root->right); }`

The `isBalanced` function first checks if the root is `NULL`. If it is `NULL`, the function returns `true` because an empty tree is always height-balanced.

If the root is not `NULL`, we calculate the height of the left and right subtrees using the `height` function. We then check if the absolute difference between the heights is greater than 1. If it is, the function returns `false` because the tree is not height-balanced.

If the difference between the heights is less than or equal to 1, we recursively call `isBalanced` on the left and right subtrees. If both subtrees are height-balanced, the function returns `true`. Otherwise, if either subtree is not height-balanced, the function returns `false`.

The time complexity of this solution is O(n^2) in the worst case because we may need to calculate the height of each node in the binary tree, and each height calculation takes O(n) time in the worst case. The space complexity is O(n) because we use recursion to traverse the binary tree and store the maximum height of each subtree on the call stack.

However, we can optimize the time complexity to O(n) by calculating the height of each node only once. We can do this by modifying the `height` function to check if the subtree rooted at a node is height-balanced and return the height of the subtree at the same time. This avoids redundant calculations of the subtree height.

Here is the optimized `height` function:
`int height(TreeNode* node, bool& balanced) { if (!node) { return 0; } int leftHeight = height(node->left, balanced); int rightHeight = height(node->right, balanced); if (abs(leftHeight - rightHeight) > 1) { balanced = false; } return 1 + max(leftHeight, rightHeight); }`

We add a boolean parameter `balanced` to the `height` function to indicate if the subtree rooted at a node is height-balanced. If the difference between the heights of the left and right subtrees is greater than 1, we set `balanced` to `false`.

Here is the modified `isBalanced` function using the optimized `height` function:
`bool isBalanced(TreeNode* root) { bool balanced = true; height(root, balanced); return balanced; }`

The `isBalanced` function initializes `balanced` to `true` and calls the `height` function on the root. The function then returns the value of `balanced`.

With the optimized `height` function, the time complexity of this solution is O(n) in the worst case, and the space complexity is O(n) due to the recursion.

## Step by Step Implementation For Balanced Binary Tree

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
//check if tree is empty
if(root == null)
return true;

//get the height of left and right sub-trees
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);

//check if the difference in height of left and right sub-trees is not more than 1 and
//that the left and right sub-trees are balanced
return (Math.abs(leftHeight - rightHeight) <= 1) && isBalanced(root.left) && isBalanced(root.right);
}

//function to get the height of a tree
public int getHeight(TreeNode root){
//check if tree is empty
if(root == null)
return 0;

//if tree is not empty, return the height of the tree by recursively
//calculating the height of the left and right sub-trees
return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}
}```
```class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
# A tree is balanced if the difference in the depths
# of its left and right subtrees is not more than 1.
# An empty tree is balanced.

# Return True if the tree is balanced, False otherwise.
if not root:
return True
return (abs(self.depth(root.left) - self.depth(root.right)) <= 1
and self.isBalanced(root.left)
and self.isBalanced(root.right))

def depth(self, root):
# Return the depth of the tree.
if not root:
return 0
return 1 + max(self.depth(root.left), self.depth(root.right))```
```var isBalanced = function(root) {
if (!root) return true;

function getHeight(node) {
if (!node) return 0;
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}

return Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
};```
```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isBalanced(TreeNode* root) {
// An empty tree is balanced by definition
if (root == nullptr) {
return true;
}

// Check if the subtrees are balanced, and if the
// difference in their heights is no more than 1.
return isBalanced(root->left) &&
isBalanced(root->right) &&
abs(getHeight(root->left) - getHeight(root->right)) <= 1;
}

int getHeight(TreeNode* root) {
// An empty tree has height -1
if (root == nullptr) {
return -1;
}

// The height of a tree is the maximum height of its subtrees
// plus 1 (for the root node).
return 1 + max(getHeight(root->left), getHeight(root->right));
}
};```
```/**
* Definition for a binary tree node.
* public class TreeNode {
*     public int val;
*     public TreeNode left;
*     public TreeNode right;
*     public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public bool IsBalanced(TreeNode root) {
// Base case
if (root == null) {
return true;
}

// Recursive case
int heightDiff = GetHeight(root.left) - GetHeight(root.right);
if (Math.Abs(heightDiff) > 1) {
return false;
} else {
return IsBalanced(root.left) && IsBalanced(root.right);
}
}

private int GetHeight(TreeNode root) {
// Base case
if (root == null) {
return 0;
}

// Recursive case
return 1 + Math.Max(GetHeight(root.left), GetHeight(root.right));
}
}```

Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]