Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Solution Approach
3.1.
C++ implementation
3.2.
Complexities
3.2.1.
Time complexity
3.2.2.
Space complexity
4.
Frequently asked questions
5.
Key Takeaways
Last Updated: Mar 27, 2024

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

Author Shreya Deep
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

A red-black tree is a form of self-balancing binary search tree in which each node has a further bit, and that bit is regularly interpreted because of the coloration (red or black). A property of red-black is that the maximum height of any node is not larger than twice the minimum height of the same node. This article will discuss a method to check if a given binary search tree follows that property or not. 

For more information on red-black trees, refer to Introduction To Red-Black Trees

Problem Statement

Given a binary search tree, check if it follows the property that the maximum height of any node is not larger than twice the minimum height of the same node. 

For example

Input

Output

Balanced

Explanation: In the above Tree:

  • Node 4 has a minimum height of 2, and the maximum height is 4. Since 4<=2*2, this node follows the property.
  • Node 2 has a minimum height of 1, and the maximum height is 1. Since 1<=2*1, this node follows the property.
  • Node 5 has a minimum height of 2, and the maximum height is 3. Since 2<=2*3, this node follows the property.
  • Node 1 has a minimum height of 1, and the maximum height is 2. Since 2<=2*1, this node follows the property.
  • Node 0 has a minimum height of 1, and the maximum height is 1. Since 1<=2*1, this node follows the property.
  • Node 6 has a minimum height of 1, and the maximum height is 1. Since 1<=2*1, this node follows the property.

Thus, each node follows the property here, and therefore we say that the Tree is balanced.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
    }
}

Output

Balanced

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 treenormal bst to balanced bstbalanced 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!

Previous article
Insertion in Left-Leaning Red-Black Tree
Next article
Find the largest K for every Array element such that at least K prefixes are ≥ K.
Live masterclass