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) {
    // Write your code here.
	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;
}