# Height balanced binary tree

A binary tree is height balanced if for each node in the tree, the difference between the height of its left subtree and the height of its right subtree is at most 1.

Let us use the following problem statement as an example to learn about the height balanced binary tree data structure.

## Problem

You are given the root node of a binary tree. Write a function that returns true if this binary tree data structure is height balanced and false if it isn’t.

To solve this problem, i will use recursion and backtracking that runs in O(n) time and O(n) space where n is the number of nodes in our binary tree.

## Solution Algorithm Explained

In solving this problem, we will make two recursive call on the left child and on the right child of each node and during backtracking, we will count the left edge(s) and right edge(s) of each node; if the difference of subtracting the left count from the right count is between 0 – 1 (which is the accepted range), then we return true else we return false.

Note that as we backtrack from one node to another, we must carry forward the count of either the left count or the right count – depending on which side is greater – and add this count to either the left count or right count of the next node edge – depending on which side of the node we arrive on during our backtracking. Please refer to the code to understand, on the code you will find a variable named: forwardsum, just observe what i am doing with this variable to understand my explanation here.

## Sample Input/Output

The second sample output is false because node’s 5 right child edges count is 3 against its left child’s count which is 1, 3 -1 == 2 and from our description above: A binary tree is height balanced if for each node in the tree, the difference between the height of its left subtree and the height of its right subtree is at most 1 – i.e between 0 to 1.

## Code Example in c++

``````bool heightBalancedBinaryTree(BinaryTree *root, int leftcnt=0, int rightcnt=0) {
static bool result = false;
static int forwardsum = 0;
static bool done = false;

if(root == nullptr) return false;
if(done == true) return false;

result = heightBalancedBinaryTree(root->left, leftcnt, rightcnt);
if(done == true) return false;
if(result == false){
leftcnt = 0; forwardsum = 0; result = false;
}else{
leftcnt = 1 + forwardsum;
}
result = heightBalancedBinaryTree(root->right, leftcnt, rightcnt);
if(done == true) return false;
if(result == false){
rightcnt = 0; forwardsum = 0; result = false;
}else{
rightcnt = 1 + forwardsum;
}

if(leftcnt > rightcnt) forwardsum = leftcnt;
if(rightcnt > leftcnt) forwardsum = rightcnt;
if(rightcnt == leftcnt) forwardsum = rightcnt;

int diff = abs(leftcnt - rightcnt);
if(diff >= 0 && diff <= 1){
return result = true;
}else{
done = true;
return result = false;
}

return result;
}``````

## lazy bartender problem solution

Daily Coding Problem: Problem #297 [Medium] This problem was asked by Amazon. At a popular bar, each customer…

## Finding Duplicates in a String Using Bitwise Operations – in c/c++

In this tutorial i am going to show you how to find duplicates in a string using bitwise…

## Remove All Occurrences Of An Element From Array In c – Interview Question

Remove All Occurrences Of An Element From Array In c is a tutorial aimed at showing how to…

## bfs and dfs program in c++ with output

In this tutorial, i will show you bfs and dfs program in c++ with output. The main difference…

## Coin change problem all combinations in javascript

In this solution, we will be exploring the option of going through all combination to count the number…

## How To Calculate Time Complexity And Space Complexity Of An Algorithm – Big O Notation Examples

How to calculate time complexity and space complexity of an algorithm show developers who are new to the…