Check if a Binary Tree is Height-Balanced or Not

Posted in

Vinay Khatri
Last updated on September 8, 2024

Problem

Given a binary tree. You need to check if it is height-balanced or not. A tree is height-balanced if the absolute difference between the height of the left and right subtrees is not more than 1.

Sample Output

`YES`

Explanation

Each node’s left and right subtree difference does not exceed 1.

Approach

We can use DFS to solve this problem. We go to the depth of the tree (leaf nodes) and keep returning heights to the parent nodes. The height returned by a child to its parent would be 1 greater than the maximum height of this child. This way, we keep track of the height difference of each node’s subtrees. The child returns height to its parent when we backtrack. For instance, if the tree is

```             1
/     \
2       3

```

1 -> 2 -> NULL, NULL returns 0 2 -> NULL, NULL returns 0 (Now backtrack and return 1+max(2->left, 2->right)) 1 will now have height of its left subtree as 1 1 -> 3 -> NULL, NULL returns 0 3 -> NULL, NULL returns 0 (Now backtrack and return 1+max(3->left, 3->right)) 1 will now have height of its right subtree as 1 The absolute difference would be 1-1=0 which is height-balanced.

Complexity Analysis

The time complexity would be O(N), and the space complexity would also be O(N) due to the call stack.

C++ Programming

```#include<bits/stdc++.h>
using namespace std;

struct TreeNode
{
int val;
TreeNode *left, *right;

TreeNode(int val)
{
this->val = val;
this->left = this->right = nullptr;
}
};

int dfs(TreeNode* root, bool &ok)
{
// if NULL node found
if (root == nullptr || !ok) {
return 0;
}

// get the height of the left subtree
int left = dfs(root->left, ok);

// get the height of the right subtree
int right = dfs(root->right, ok);

if (abs(left - right) > 1) {
ok = false;
}

// return height of subtree rooted at the current node
return max(left, right) + 1;
}

bool dfs(TreeNode* root)
{
bool ok = true;
dfs(root, ok);
return ok;
}

int main()
{
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);

if (dfs(root)) {
cout << "Tree is balanced";
}

else {
cout << "Tree is not balanced";
}
return 0;
}```

Output

`Tree is balanced`

Java Programming

```import java.util.concurrent.atomic.AtomicBoolean;

class TreeNode
{
int val;
TreeNode left = null, right = null;

TreeNode(int val) {
this.val = val;
}
}

class Main
{
public static int dfs(TreeNode root, AtomicBoolean ok)
{
// if node is NULL
if (root == null || !ok.get()) {
return 0;
}
// left subtree height
int left = dfs(root.left, ok);

// right subtree height
int right = dfs(root.right, ok);

if (Math.abs(left - right) > 1) {
ok.set(false);
}

// return height of subtree rooted at the current node
return Math.max(left, right) + 1;
}

public static boolean dfs(TreeNode root)
{
AtomicBoolean ok = new AtomicBoolean(true);
dfs(root, ok);
return ok.get();
}

public static void main(String[] args)
{
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);

if (dfs(root)) {
System.out.print("Tree is balanced");
}

else {
System.out.print("Tree is not balanced");
}
}
}```

Output

`Tree is balanced`

Python Programming

```class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right

def dfs(root, ok=True):
# if node is NULL
if root is None or not ok:
return 0, ok

# get the height of the left subtree
left, ok = dfs(root.left, ok)

# get the height of the right subtree
right, ok = dfs(root.right, ok)

if abs(left - right) > 1:
ok = False

# return height too parent
return max(left, right) + 1, ok

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

if dfs(root)[1]:
print("Tree is balanced")
else:
print("Tree is not balanced")
```

Output

`Tree is balanced`

People are also reading: