• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Find if a binary tree is height balanced ?

January 12, 2015 by Dhaval Dave

A Height Balanced Tree is tree where for each node this condition is true.
– The difference between heights of left subtree and right subtree for any node is not more than 1.So we can say that a tree T is Height Balanced when
– Left Sub Tree of T is height balanced
– Right Sub Tree of T is height balanced
and for each node this above condition is true :P
So now
Approach 1) 
– Start from root.
– find height of Left and Right Subtree.
– If difference is <2
contiue
– else break
call same procedure for left and right child of node.Pseudo Code 

isHeightBalanced ( node root)
{
if (root==null) return 1;
lh = height ( root -> left )
rh = height ( root -> right )
if(lh-rh<2 || rh-lh<2) {
  return 1 && ( isHeightBalanced ( root -> left ) && isHeightBalanced( root -> right ) )
}
else 
   return 0;
}

as Complexity of above code is O(n2) ,  { for each node recursively finding height and recursively finding height balacned }
We can think that while calculating height itself why not to find is a node is heightBalanced or not.
This would be topdown approch.

Approach 2)

bool isHeightBalanced(struct node *root, int* height)
{
int lh = 0, rh = 0; 
int l = 0, r = 0;

if(root == NULL)
  {
    *height = 0;
     return 1;
  }//basecase

l = isBalanced(root->left, &lh);
r = isBalanced(root->right,&rh);
//call recursively

*height = (lh > rh? lh: rh) + 1;
 if((lh - rh >= 2) || (rh - lh >= 2)) return 0;
 else return l&&h;

 }


//See *height is calculated and its reference would be either &lh or &rh
//Hence we calculated height of tree from root and specified lh/rh height for parent.
//so that lh-rh can be calculated easily

Code :

/* program to check if a tree is height-balanced or not */
#include<stdio.h>
#include<stdlib.h>
#define bool int

struct node
{
  int data;
  struct node* left;
  struct node* right;
};
struct node* newNode(int data)
{
  struct node* node = (struct node*)
  malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;
  return(node);
}
bool isBalanced(struct node *root, int* height)
{
  int lh = 0, rh = 0; 
  int l = 0, r = 0;
	
  if(root == NULL)
  {
	*height = 0;
	return 1;
  }

  l = isBalanced(root->left, &lh);
  r = isBalanced(root->right,&rh);

  height = (lh > rh? lh: rh) + 1;
  if((lh - rh >= 2) || (rh - lh >= 2))
	return 0;
  else return l&&r;
}

int main()
{
 int height = 0;
 struct node *root = newNode(1); 
 root->left = newNode(2);
 root->right = newNode(3);
 root->left->left = newNode(4);
 root->left->right = newNode(5);
 root->right->left = newNode(6);
 root->left->left->left = newNode(7);

 if(isBalanced(root, &height))
	printf("Tree is balanced");
 else
	printf("Tree is not balanced"); 
 return 0;
}

See Working code at http://ideone.com/QTnTNe

Similar Articles

Filed Under: Amazon Interview Question, Interview Questions, Microsoft Interview Questions, problem Tagged With: Binary Tree, tree

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

ADOBE Aptitude C Language Test

Python List

C++ OOPs Part2

Handle duplicates in Binary Search Tree

strtok()

Facebook Interview Question : Interleave List

Reverse a Linked List in groups of given size

Circular Linked List

Maximum sum contiguous subarray of an Array

Find the element that appears once others appears thrice

Interfaces in C++ (Abstract Classes in C++)

Python Dictionaries

SAP Off Campus Hiring_ March 2015 Verbal Skills

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)

C Program for TAIL command of UNIX

Generate largest number arranging a no. of given non negative integer numbers

Sequence Finder Dynamic Programming

CodeChef Code SGARDEN

SAP Interview Questions

Binary Tree in Java

BlueStone E-commerce Interview Experience

Convert number to words java

Best Java Book | Top Java Programming Book for Beginners

Get Minimum element in O(1) from input numbers or Stack

Printing intermediate Integers between one element & next element of array

Find position of the only set bit

Singly linked list

N teams are participating. each team plays twice with all other teams. Some of them will go to the semi final. Find Minimum and Maximum number of matches that a team has to win to qualify for finals ?

Find min element in Sorted Rotated Array (Without Duplicates)

Copyright © 2025 · Genesis Framework · WordPress · Log in