How to check if a red-black tree is balanced

Check if a red-black tree is balanced

A red-black tree is a type of self-balancing binary tree.

Note: Read more about a red-black tree here.

In this Answer, we'll learn how to check if a tree is balanced. A red-black tree is balanced if the following conditions are met:

  1. For every node in the tree, the number of black nodes on both subtrees is the same.

  2. There are no two consecutive red nodes.

  3. The root node is black.

Code

class Node:
def __init__(self, value, color=RED):
self.value = value
self.left = None
self.right = None
self.color = color
class RedBlackTree:
def __init__(self):
self.root = None
def _numBlack(self, root):
if not root:
return 0
black_left = self._numBlack(root.left)
black_right = self._numBlack(root.right)
if black_left != black_right or black_left == -1:
return -1
if root.color == BLACK:
return 1 + black_left
else:
return 0 + black_left
def isBalanced(self):
if not self.root or self.root.color != BLACK:
return False
black_left = self._numBlack(self.root.left)
black_right = self._numBlack(self.root.right)
if black_left != black_right or black_left == -1:
return False
return True
tree = RedBlackTree()
tree.root = Node(3, BLACK)
tree.root.right = Node(4, RED)
tree.root.left = Node(2, RED)
tree.root.left.right = Node(2.5, BLACK)
print("The tree is", "balanced" if tree.isBalanced() else "not balanced")

Explanation

  • Lines 1–6: We define a Node class that stores a node.

  • Lines 12–26: We define a function isBalanced() that calls _numBlack(). The function _numBlack() returns the number of black nodes on any single path from that node. The function isBalanced() then checks if there are an equal number of black nodes on both left and right subtree and returns a boolean value.

  • Lines 34–40: We manually define a red-black tree and call the function isBalanced() to see if the tree is balanced.

Note: You may change the structure of the tree to see how isBalanced() behaves.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved