Determine if a binary tree satisfies the height-balanced property of a red–black tree
Write an efficient algorithm to determine if a binary tree satisfies the height-balanced property of the red–black tree or not.
The red–black tree’s height-balanced property states that the path from the root to the farthest leaf is no more than twice as long as a path from the root to the nearest leaf. In other words, the maximum height of any node in a tree is not greater than twice its minimum height.
For example, the following tree is height-balanced:
In contrast, the following tree violates the red–black tree property at node 3:
A simple solution would be to calculate the maximum and minimum height of every node in the tree and determine if the subtree rooted at that node is balanced or not. If the height-balanced property is satisfied for every subtree, the binary tree enforces the red–black tree’s height-balanced property. For a tree containing n elements, this solution takes O(n2) time since, for every node, we are traversing the whole subtree rooted at that node.
The main challenge is to perform this in a single tree traversal, i.e., in O(n) time. The idea is to perform a postorder traversal on the binary tree and calculate the maximum and minimum height for every node in a bottom-up fashion. Then we can easily check if the height-balanced property of the red–black tree is satisfied for every node in the tree or not.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <utility> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Recursive function to determine if the given binary tree // satisfies the height-balanced property of the red–black tree or not. // It takes the reference to the `rootMax` variable for storing the // maximum height of the root node. bool isHeightBalanced(Node* root, int &rootMax) { // Base case if (root == nullptr) { return true; } // to hold the maximum height of the left and right subtree int leftMax = 0, rightMax = 0; // proceed only if both left and right subtrees are balanced if (isHeightBalanced(root->left, leftMax) && isHeightBalanced(root->right, rightMax)) { // calculate the minimum and maximum height of the left and right subtree int rootMin = min(leftMax, rightMax) + 1; rootMax = max(leftMax, rightMax) + 1; // return true if the root node is height-balanced return (rootMax <= 2*rootMin); } // return false if either left or right subtree is unbalanced return false; } int main() { /* Construct the following tree 1 / \ 2 3 / / \ 4 5 6 / \ 7 8 / \ 9 10 */ Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->right->left = new Node(5); root->right->right = new Node(6); root->right->left->left = new Node(7); root->right->left->right = new Node(8); root->right->left->left->left = new Node(9); root->right->left->left->right = new Node(10); int rootMax = 0; if (isHeightBalanced(root, rootMax)) { cout << "Height-balanced"; } else { cout << "Not height-balanced"; } return 0; } |
Output:
Height-balanced
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
import java.util.concurrent.atomic.AtomicInteger; // A class to store a binary tree node class Node { int data; Node left, right; Node(int data) { this.data = data; } } class Main { // Recursive function to determine if the given binary tree // satisfies the height-balanced property of the red–black tree or not public static boolean isHeightBalanced(Node root, AtomicInteger rootMax) { // Base case if (root == null) { return true; } // to hold the maximum height of the left and right subtree AtomicInteger leftMax = new AtomicInteger(0); AtomicInteger rightMax = new AtomicInteger(0); // proceed only if both left and right subtrees are balanced if (isHeightBalanced(root.left, leftMax) && isHeightBalanced(root.right, rightMax)) { // calculate the minimum and maximum height of the left and right subtree int rootMin = Math.min(leftMax.get(), rightMax.get()) + 1; rootMax.set(Math.max(leftMax.get(), rightMax.get()) + 1); // return true if the root node is height-balanced return (rootMax.get() <= 2*rootMin); } // return false if either left or right subtree is unbalanced return false; } public static void main(String[] args) { /* Construct the following tree 1 / \ 2 3 / / \ 4 5 6 / \ 7 8 / \ 9 10 */ Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.right.left = new Node(5); root.right.right = new Node(6); root.right.left.left = new Node(7); root.right.left.right = new Node(8); root.right.left.left.left = new Node(9); root.right.left.left.right = new Node(10); AtomicInteger rootMax = new AtomicInteger(0); if (isHeightBalanced(root, rootMax)) { System.out.println("Height-balanced"); } else { System.out.println("Not height-balanced"); } } } |
Output:
Height-balanced
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
# A class to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right class MutableInt: def __init__(self, data): self.value = data def set(self, data): self.value = data def get(self): return self.value # Recursive function to determine if the given binary tree # satisfies the height-balanced property of the red–black tree or not def isHeightBalanced(root, rootMax=MutableInt(0)): # Base case if root is None: return True # to hold the maximum height of the left and right subtree leftMax = MutableInt(0) rightMax = MutableInt(0) # proceed only if both left and right subtrees are balanced if isHeightBalanced(root.left, leftMax) and isHeightBalanced(root.right, rightMax): # calculate the minimum and maximum height of the left and right subtree rootMin = min(leftMax.get(), rightMax.get()) + 1 rootMax.set(max(leftMax.get(), rightMax.get()) + 1) # return true if the root node is height-balanced return rootMax.get() <= 2 * rootMin # return false if either left or right subtree is unbalanced return False if __name__ == '__main__': ''' Construct the following tree 1 / \ 2 3 / / \ 4 5 6 / \ 7 8 / \ 9 10 ''' root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.right.left = Node(5) root.right.right = Node(6) root.right.left.left = Node(7) root.right.left.right = Node(8) root.right.left.left.left = Node(9) root.right.left.left.right = Node(10) if isHeightBalanced(root): print('Height-balanced') else: print('Not height-balanced') |
Output:
Height-balanced
The time complexity of the above solution is O(n), where n is the total number of nodes in the binary tree. The auxiliary space required by the program is O(h) for the call stack, where h is the height of the tree.
Calculate the height of a binary tree with leaf nodes forming a circular doubly linked list
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)