Check if a given Binary Search Tree is height-balanced like a Red-Black Tree

Solution Approach

The idea is to traverse the entire tree only once. And at each node, find if its left and right subtrees are balanced or not and whether the maximum height is greater or equal to double of its minimum height or not. 

Also, after finding this, we will need to return it because these values, as those, will be required by the node's ancestors to calculate their respective values. Thus, we return the bool value of whether the Tree is balanced and pass the integers that store the minimum and maximum heights of the Tree by reference so that we can access them later. But, how do we calculate the value of the minimum and maximum height?

To calculate the maximum and minimum height values, we will need its subtrees' minimum and maximum heights (both left and right). The calculation formula will be:

Minimum height = min(minimum height of the left subtree, minimum height of the right subtree)+1

Maximum height = min(maximum height of the left subtree, maximum height of the right subtree)+1

Note: For a NULL node, the minimum and maximum height values are both 0, and it is balanced. 

Steps of implementation are:

• Construct a Binary Tree
• Call the function isBalanced, which returns if the Tree is balanced or not. If the returned value is true, print "Balanced." Otherwise, print "Not balanced."
• In the function "isBalanced":
  • If the node is a NULL node, return false, and the minimum and maximum height will be 0
  • Declare four variables to store the minimum and maximum of the left and the right subtrees
  • If the left or the right subtrees are itself not balanced, the subtree rooted at the current node can't be balanced, so return false
  • Now, since we know that the left and the right subtrees are balanced, calculate the minimum and the maximum heights of the Tree rooted at the current node
  • Check if the maximum height is less than or equal to twice the minimum height. If yes, return true. Otherwise false

C++ implementation

#include<bits/stdc++.h>
using namespace std;
template <typename T>
/*
  Class for BinaryTreeNode
*/  
class BinaryTreeNode{
    public:
    /*
        Data of the node
    */
    T data;
    /*
        Left of the node
    */
    BinaryTreeNode* left;
    /*
        Right of the node
    */
    BinaryTreeNode* right;
    /*
        Constructor for assigning the data to the current node
    */
    BinaryTreeNode(T data){
        this->data=data;
        left=NULL;
        right=NULL;
    }
};


bool isbalanced(BinaryTreeNode<int>* root, int &minimum_height, int &maximum_height){
    /*
        If the node is a NULL node, return false, and the minimum and maximum height will be 0.
    */
    if(root==NULL){
        minimum_height = 0;
        maximum_height = 0;
        return true;
    }
    /*
        Declare four variables to store the minimum and maximum of the left and the right subtrees
    */
    int left_subtree_minimum_height, left_subtree_maximum_height;
    int right_subtree_minimum_height, right_subtree_maximum_height;
    /*
        If the left or the right subtrees are themselves not balanced, the subtree rooted at the current node can't be balanced, so return false.
    */
    if(isbalanced(root->left,left_subtree_minimum_height,left_subtree_maximum_height)==false){
        return false;
    }
    if(isbalanced(root->right,right_subtree_minimum_height,right_subtree_maximum_height)==false){
        return false;
    }
    /*
        Now, since we know that the left and the right subtrees are balanced, calculate the minimum and the maximum heights of the tree rooted at the current node.
    */
    minimum_height = min(left_subtree_minimum_height,right_subtree_minimum_height)+1;
    maximum_height = max(left_subtree_maximum_height,right_subtree_maximum_height)+1;
    /* 
        Check if the maximum height is less than or equal to twice the minimum height. If yes, return true. Otherwise false.
    */
    if(maximum_height<=2*minimum_height){
        return true;
    }
    else{
        return false;
    }
}
 

int main()
{
    
    /*
        Construct a Binary Tree
    */
    BinaryTreeNode<int> *root = NULL;
    root = new BinaryTreeNode<int>(4);
    root->left = new BinaryTreeNode<int>(2);
    root->right = new BinaryTreeNode<int>(5);
    root->right->left = new BinaryTreeNode<int>(1);
    root->right->right = new BinaryTreeNode<int>(3);
    root->right->left->left = new BinaryTreeNode<int>(6);
    int minimum_height, maximum_height;
    /*
        Call the function isBalanced which returns if the tree is balanced or not. If the returned value is true, print "Balanced". Otherwise, print "Not balanced".
    */
    if(isbalanced(root, minimum_height,maximum_height)==true){
        cout<<"Balanced"<<endl;
    }
    else{
        cout<<"Not balanced"<<endl;
    }
}

You can also try this code with Online C++ Compiler

Run Code

Output

Balanced

You can also try this code with Online C++ Compiler

Run Code

Complexities

Time complexity

O(n), where n is the number of nodes in the Tree

Reason: Here, we are traversing the Tree once( each node at most once only), and therefore, the time taken is O(n).

Space complexity

O(1)

Reason: All the spaces are constant. The space taken up by the recursion stack is O(n), but we don't consider it because it is not auxiliary space.

Check out this problem - Diameter Of Binary Tree

Frequently asked questions

1. What is a Red-Black Tree?
   Red-Black Tree is a variety of Binary Trees in which the last node of the Tree is Null.
    
2. What is the height-balanced property of Red-Black Tree?
   The height-balanced property of Red-Black Tree is that for a tree to be balanced, for each node, the maximum height of the Tree rooted at that node should be less than or equal to the minimum height of the Tree rooted at that node.
    
3. What are binary search trees?
   Binary search trees are trees in which, for each node, the node's value is larger than the maximum value in its left node and smaller than the minimum value in its right subtree.
    
4. What is the height of a tree?
   The height of a tree is the maximum number of edges in the paths from the root to the Tree's leaf.
    
5. How to calculate the height of a tree?
   The height of a tree is the (maximum of the height of its left and right subtree) +1.

Key Takeaways

This article discussed the method to check if a given BST is height-balanced like a red-black tree. The solution required a traversal of the Tree. Similar problems are: is a height-balanced binary tree, normal bst to balanced bst, balanced binary tree, and the number of balanced binary trees. You should practice these to get a good grasp on this kind of problem.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!