RUN


Problem

A binary tree in which the left and right subtrees of every node differ in height by no more than 1 is called a height-balanced binary tree. Check if the given tree is height-balanced or not.

Brute Force Approach

We calculate the height at every node and check if the tree is height-balanced or not.

TC – O(N2)

Better Approach

We will keep track left and right height of the subtree in a variable at each node and if at any node the absolute difference of left and right height is greater than 1 we’ll return false.

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

struct Node{
	int data;
  	Node* left;
  	Node* right;
  	Node(int data){
    	this->data = data;
      	left = right = NULL;
    }
};

int checkBalanced(Node* root, bool &result){
	if(!root) return 0;

  	int lh = checkBalanced(root->left, result);
  	int rh = checkBalanced(root->right, result);
	
  	int currHeight = max(lh, rh) + 1;
  	int leftRightSubtreeHeightDiff = abs(lh - rh);
  	
  	if(leftRightSubtreeHeightDiff > 1) result = false;
  	
  	if(!result) return 0;
  
  	return currHeight;
}


int main() {
/*
         1
       /    \
      2      3
    /   \   /  \
   4     5 6    7
*/
    struct Node* root = new Node(1);
  	root->left = new Node(2);
  	root->left->left = new Node(4);
  	root->left->right = new Node(5);
  	root->right = new Node(3);
  	root->right->left = new Node(6);
  	root->right->right = new Node(7);
  	bool result = true;
  	checkBalanced(root, result);
  	cout<<result;
    return 0;
}

TC – O(N)

Report Error/ Suggestion

Related Posts:



CopyRight © 2020

CopyRight © 2020