Balanced Binary Tree in Python

Before talking about the height balanced binary tree, let’s understand what exactly is meant by the height of the binary tree.

Height of a binary tree = Count of edges between the root node and the farthest node

If a node is null or None, it’s height is considered -1, just imagine a tree which is beneath the surface of the earth so it’s height will be considered negative :)

A height balanced Binary Tree has the following properties ::

1. At every node in the tree, the right sub-tree and left sub-tree should be balanced trees as well
2. The difference in the height of the right sub-tree and left sub-tree should not exceed 1

Between Nodes and Trees

In programming how we pronounce something in mind may lead to different results. Just for an example:

1. A tree is composed of Nodes vs
2. A tree is nothing but Nodes connected together

may lead to 2 different thoughts in the mind of a programmer thinking of writing an objected oriented code for the problem.

I decided to go with point #2 which says that Tree is nothing but Nodes connected together. So at least for this article, we’re going to write code based on that assumption. ( feel free to comment if you think otherwise, I’m open to change )

Now let’s build some classes !!

Tree Class

I planned to name the class NodeTree and it has 3 attributes viz value, right and left. Value is the value of the current node and right, left corresponds to the right and left sub-trees.

class NodeTree:
    def __init__(self, value, right=None, left=None):
        self.value = value
        self.right = right
        self.left = left

Representing Measurements

Measurements is a class which represents the different measures of a tree e.g. height, is_balanced etc

class Measurements:
    def __init__(self, height, balanced):
        self.height = height
        self.balanced = balanced

Perform the Calculations

Think of this class as an equivalent of a measuring tape or any measuring apparatus in general which takes the object and performs some calculations on it.

class Guage:
@staticmethod
    def measure(tree):
        if tree is None:
            return Measurements(-1, True)
        else:
            left_tree_measures = Guage.measure(tree.left)
            right_tree_measures = Guage.measure(tree.right)
# check conditions
            left_right_balance = left_tree_measures.balanced and right_tree_measures.balanced
            height_diff = abs(left_tree_measures.height -
                              right_tree_measures.height)
height = max(left_tree_measures.height,
                         right_tree_measures.height) + 1
            balanced = left_right_balance and height_diff <= 1
            return Measurements(height, balanced)

Combining the Pieces

Combining all the classes together and testing whether the pieces work together in harmony or not.

class NodeTree:
    def __init__(self, value, right=None, left=None):
        self.value = value
        self.right = right
        self.left = left
class Measurements:
    def __init__(self, height, balanced):
        self.height = height
        self.balanced = balanced
class Guage:
    @staticmethod
    def measure(tree):
        if tree is None:
            return Measurements(-1, True)
        else:
            left_tree_measures = Guage.measure(tree.left)
            right_tree_measures = Guage.measure(tree.right)
            #check conditions
            left_right_balance = left_tree_measures.balanced and 
                                 right_tree_measures.balanced
            height_diff = abs(left_tree_measures.height -
                              right_tree_measures.height)
            height = max(left_tree_measures.height,
                         right_tree_measures.height) + 1
            balanced = left_right_balance and height_diff <= 1
            return Measurements(height, balanced)
if __name__ == "__main__":
    nt_5 = NodeTree(5, None, None)
    nt_4 = NodeTree(4, nt_5, None)
    nt_2 = NodeTree(2, nt_4, None)
    nt_3 = NodeTree(3, None, None)
    nt_root = NodeTree(1, nt_2, nt_3)
    nt_measurements = Guage.measure(nt_root)
    print(nt_measurements.height)
    print(nt_measurements.balanced)

Summary

In this article we learned how to tell whether a given binary tree is height balanced or not. If you’re interested in Data Structures and Algorithms, I’ve also written about Graph theory and BFS in Python .

Next Steps

1. In case anything is not clear in the article, feel free to ask in comments.
2. In case you would like to suggest edits etc, again comment
3. If you want to see a specific topics covered in the upcoming posts, feel free to comment :)