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

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.

[{"selector":"#anim-942cb1e6-a2ef-4830-8df0-4e4812c14d51","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-a62176de-5e0c-4447-9557-3cec42cae621","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-77052898-52cf-4bf3-9e99-dc3e69e8a246 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Get started now Click here

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.

[{"selector":"#anim-a9aafa0d-09a8-4780-876f-cc6b690eaebc [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-0db4ec49-8506-417d-999c-6bf12da44a98","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-ace6e220-1de9-48a7-a658-8a216771f460","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-f62ae1be-6456-4b43-b996-372f5352c1bf","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-ebe0ba73-9dc1-423d-a388-2756c1e4dc43","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Check out the examples for better understanding Click here

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.

[{"selector":"#anim-b72dc375-ba9d-499c-9489-2fdacfa4eac9","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-612785b9-1bca-471b-ad56-ee25da0ec842","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-f13ef5df-174b-45d5-903f-4cc6130d9c6c [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-f224cddd-9b73-4539-95a3-2e383e688e21","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-cdfa112b-1e3f-4ea3-b934-b5be559da5ea","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Want to see code implementation? Click here

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

[{"selector":"#anim-b43f286d-6904-4972-b6d5-fd8545865310","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-8ce96dda-f149-47ce-8464-b1f6df042d89","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-468b750f-36fc-4bd2-9637-4e649e8d00bc [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Want to explore other approach? Click here

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.

[{"selector":"#anim-5b592744-be78-4e53-83bc-00647f78a4f0 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-da9c442e-925d-4b64-8358-763977293d04","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-f69baf03-97a3-4195-aeeb-38ca4e8ca4c4","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-ea7c54b7-2cd1-411f-a469-dbf30fe9dd61","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-5ffae18b-295e-4765-a043-9dc8ef2fdc9f","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Want to see code implementation? Click here

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.

[{"selector":"#anim-f725392b-a574-4d79-9542-1bd7d7a2788f","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-2537c85a-8d48-438c-ae7f-c00940e247de","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-2f0d30ed-ac6b-47d7-b255-fc35c207f2fb [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-44b9f10f-9a02-47dd-905e-55896712868d","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-86b702bf-a7c4-4b02-98df-ae672e4bf9dd","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Want to see code implementation? Click here

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

[{"selector":"#anim-38dd99c3-8fd3-40b1-b2a0-45a7adade240","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-f3f5a808-f25d-47c0-b667-6723bc30471c","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-be126824-384a-40d1-b616-2dc25360131b [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(-3.552713678800501e-15%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Want to see code implementation? Click here

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

[{"selector":"#anim-a9936de1-03e2-4677-9c42-410a7c9fcda6","keyframes":{"opacity":[0,1]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-526d8d04-3ffd-4bf1-a002-21c1cf0d1b8a","keyframes":{"transform":["translate3d(-105.86593%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-13a42119-6cbc-4f64-b601-4a9ad83d1988","keyframes":{"opacity":[0,1]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-27ba6551-23ac-402c-bc81-6a3d9ca7ad71","keyframes":{"transform":["translate3d(0px, -260.77716%, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] Click here

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

[{"selector":"#anim-48b19769-a1dc-4d67-b0ca-6d670b82a954","keyframes":{"opacity":[0,1]},"delay":0,"duration":1000,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-b5ac27c2-7678-4743-af95-ea4b4d752452","keyframes":{"transform":["translate3d(0px, -211.49618%, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":1000,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-87845422-6a9d-4ae1-ba73-ce95ca1c3d14","keyframes":{"opacity":[0,1]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-bd5f3618-fb59-4e01-9a4b-76dad930df6b","keyframes":{"transform":["translate3d(0px, -621.00265%, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] Step Up Your Game with InterviewBit Web Stories SWIPE UP

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.

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

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

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

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

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?

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

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

Are you ready to level up your coding skills?

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

“