How to Find whether a Binary Tree is Height-balanced?

A Quick Guide

Looking for a way to improve the efficiency of your data structure operations?    Learn about balanced binary trees and how they can optimize your algorithms.

Get started now

Given a binary tree, determine if is height-balanced which means that difference in height betweenleft & right subtrees of each node is no more than 1.

Problem Statement

Check out the examples for better understanding

Steps to follow-  1. Calculate the heights of left & right subtrees for each node.  2. If height difference > 1, return false.  3. Recursively check if the left & right nodes are also height-balanced.

Approach 1: Naive

Want to see code implementation?

Time Complexity: O(n * n)  Space Complexity: O(1)

Want to explore other approach?

It is same as naive approach, but optimizes complexity by calculating the height of each subtree during same recursive function call rather than using a separate function.

Approach 2: Optimal

Want to see code implementation?

Since the recursion progresses in a bottom-up manner, the height of children’s subtree can be used to compute height of current node’s subtree.   Height of current node = max(height of left subtree, height of right subtree) + 1.

How optimal approach works?

Want to see code implementation?

Time Complexity: O(n) Space Complexity: O(1)

Want to see code implementation?

Start your journey now and learn how to successfully find balanced binary tree.

Are you ready to level up your coding skills?

Step Up Your Game with InterviewBit Web Stories

Don't miss out on the chance to upskill yourself with IntervewBit's engaging web stories.