Check for Balanced Binary Tree (C++, Java, Python)

A balanced binary tree is an important data structure in optimizing search, insert, and delete operations. In this article, we will explore the concept of balanced binary trees, two different approaches to determining whether a given binary tree is height-balanced or not, and how to implement the solution.

What is the Balanced Binary Tree Problem?

In the Balanced Binary Tree problem, we are given a binary tree and we have to check whether the given binary tree is balanced or not. A binary tree is balanced when the depth of every node’s left and right subtrees differs by at most one.

Check the example of a balanced binary tree below:

As we can see the difference in heights for every subtree is not more than 1, it is balanced.

In the simplest naive approach, we will check the height of the left and right subtree for every node present in the tree for this we will traverse the tree recursively to calculate the height of the left and right subtree from every node, and whenever the condition of balanced binary tree violates, we will return false.

Naive Approach to check for balanced binary tree

We will start traversing the tree from Node 3: left height = 1 and right height = 2 absolute difference is (2-1) = 1
Node 6: left height = 0 and right height = 0 absolute difference is (0-0) = 0
PostOrder of Node 6, the left subtree (null) gives true & right subtree (null) gives true, as both are true, return true.
Node 7: left height = 1 and right height = 1 absolute difference is (1-1) = 0
Node 1: left height = 0 and right height = 0 absolute difference is (0-0) = 0
PostOrder of Node 1, the left subtree (null) gives true & right subtree (null) gives true, as both are true, return true.
Node 0: left height = 0 and right height = 0 absolute difference is (0-0) = 0.
PostOrder of Node 0, the left subtree (null) gives true & right subtree (null) gives true, as both are true, return true.
PostOrder of Node 7, the left subtree (1) gives true & right subtree (0) gives true, as both are true, return true.
PostOrder of Node 3, the left subtree (6) gives true & right subtree (7) gives true, as both are true, return true.

Overall all nodes are returning true which means our binary tree is a balanced binary tree. You can learn how to find the height of a binary tree using recursion as well.

The time complexity for this naive approach is O(N*N) because for every node height function is called which takes O(N) time hence every node is visited multiple times. The space complexity for this approach is O(1) (extra space) + O(H) recursive stack space where H is the height of the tree.

Post-order Traversal to Check Binary Tree is Balanced or Not

In the post-order traversal approach to check for a balanced binary tree, we will use the post-order traversal to recursively traverse the left subtree and the right subtree.

From this, we will calculate the height of the current node as the maximum height of its left and right subtrees, plus 1. Check if the current node is balanced by comparing the heights of its left and right subtrees. The tree is not balanced if the absolute difference is greater than 1.

Here is the step-by-step guide to doing it practically:

First, we will declare the base case of our recursive function that if the current node equals NULL, it means we have reached the end of a branch. In this case, the height of this subtree is 0.
Now we will start traversing the tree recursively with post-order calculating the height of the root node and returning to its previous call.
While obtaining each node’s post order, we will check the condition of the balance tree as we have the height of the left and right subtree.
If the tree is balanced we will simply return the height of the subtree otherwise we will return -1.
If subtree is not balanced we will simply return -1.

Let’s see an example of the same:

Post-order Traversal to check for balanced binary tree

First of all, we reached the leftmost node, Node 6: Left child = null so Left Height = 0, Right child = null so Right Height = 0, Difference is 0-0 = 0, ( 0 <= 1 ) so return height, i.e. Max(0,0) + 1 = 1.
Node 1: Left child = null so Left Height = 0, Right child = null so Right Height = 0, Difference is 0-0 = 0 , ( 0 <= 1 ) so return height , i.e. Max(0,0) + 1 = 1.
Node 0: Left child = null so Left Height = 0, Right child = null so Right Height = 0 , Difference is 0-0 = 0 , ( 0 <= 1 ) so return height , i.e. Max(0,0) + 1 = 1.
Node 7: Left child = 1 so Left Height = 1, Right child = 0 so Right Height = 1, Difference is 1-1= 0 , ( 0 <= 1 ) so return height , i.e. Max(1,1) + 1 = 2.
Node 3: Left child = 6 so Left Height = 1, Right child = 7 so Right Height = 2, Difference is 2-1= 1 , ( 1 <= 1 ) so return height , i.e. Max(2,1) + 1 = 3 .

Now we know how to do it, let’s implement it in various programming languages.

C++ Code

Below is the C++ program to check for balanced binary tree using post-order traversal:

#include<bits/stdc++.h>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    // Function to check if the tree is balanced
    bool isBalanced(TreeNode* root) {
        // Call the helper function for DFS with post-order traversal
        return dfsHeight(root) != -1;
    }

    // Helper function for DFS with post-order traversal to calculate tree height
    int dfsHeight(TreeNode* root) {
        // Base case: if the current node is NULL, return 0
        if (root == NULL) return 0;

        // Recursively calculate the height of the left subtree
        int leftHeight = dfsHeight(root->left);
        // If the left subtree is unbalanced, propagate -1 up the recursion
        if (leftHeight == -1) 
            return -1;

        // Recursively calculate the height of the right subtree
        int rightHeight = dfsHeight(root->right);
        // If the right subtree is unbalanced, propagate -1 up the recursion
        if (rightHeight == -1) 
            return -1;

        // Check if the current subtree is balanced
        if (abs(leftHeight - rightHeight) > 1)  
            return -1;

        // Return the height of the current subtree
        return max(leftHeight, rightHeight) + 1;
    }
};

int main() {
    // Constructing the tree
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(6);
    root->right = new TreeNode(7);
    root->right->left = new TreeNode(1);
    root->right->right = new TreeNode(0);

    // Creating an instance of the Solution class
    Solution solution;

    // Checking if the tree is balanced
    bool balanced = solution.isBalanced(root);

    // Output the result
    if (balanced) {
        cout << "The tree is balanced." << endl;
    } else {
        cout << "The tree is not balanced." << endl;
    }

    // Deallocating the memory
    // In a complete program, you would want to free the allocated memory for the tree nodes
    return 0;
}

Python Code

Here is the Python program to check for a balanced binary tree:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isBalanced(self, root):
        # Call the helper function for DFS with post-order traversal
        return self.dfs_height(root) != -1

    def dfs_height(self, root):
        # Base case: if the current node is None, return 0
        if root is None:
            return 0

        # Recursively calculate the height of the left subtree
        left_height = self.dfs_height(root.left)
        # If the left subtree is unbalanced, propagate -1 up the recursion
        if left_height == -1:
            return -1

        # Recursively calculate the height of the right subtree
        right_height = self.dfs_height(root.right)
        # If the right subtree is unbalanced, propagate -1 up the recursion
        if right_height == -1:
            return -1

        # Check if the current subtree is balanced
        if abs(left_height - right_height) > 1:
            return -1

        # Return the height of the current subtree
        return max(left_height, right_height) + 1

# Constructing the tree
root = TreeNode(3)
root.left = TreeNode(6)
root.right = TreeNode(7)
root.right.left = TreeNode(1)
root.right.right = TreeNode(0)

# Creating an instance of the Solution class
solution = Solution()

# Checking if the tree is balanced
balanced = solution.isBalanced(root)

# Output the result
if balanced:
    print("The tree is balanced.")
else:
    print("The tree is not balanced.")

Java Code

You can implement it in Java also:

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    // Function to check if the tree is balanced
    public boolean isBalanced(TreeNode root) {
        // Call the helper function for DFS with post-order traversal
        return dfsHeight(root) != -1;
    }

    // Helper function for DFS with post-order traversal to calculate tree height
    private int dfsHeight(TreeNode root) {
        // Base case: if the current node is null, return 0
        if (root == null)
            return 0;

        // Recursively calculate the height of the left subtree
        int leftHeight = dfsHeight(root.left);
        // If the left subtree is unbalanced, propagate -1 up the recursion
        if (leftHeight == -1)
            return -1;

        // Recursively calculate the height of the right subtree
        int rightHeight = dfsHeight(root.right);
        // If the right subtree is unbalanced, propagate -1 up the recursion
        if (rightHeight == -1)
            return -1;

        // Check if the current subtree is balanced
        if (Math.abs(leftHeight - rightHeight) > 1)
            return -1;

        // Return the height of the current subtree
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

class Main {
    public static void main(String[] args) {
        // Constructing the tree
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(6);
        root.right = new TreeNode(7);
        root.right.left = new TreeNode(1);
        root.right.right = new TreeNode(0);

        // Creating an instance of the Solution class
        Solution solution = new Solution();

        // Checking if the tree is balanced
        boolean balanced = solution.isBalanced(root);

        // Output the result
        if (balanced) {
            System.out.println("The tree is balanced.");
        } else {
            System.out.println("The tree is not balanced.");
        }

        // In a complete program, you would want to free the allocated memory for the tree nodes
    }
}

The time complexity of the post-order traversal approach to check whether a binary tree is balanced or not is O(N), where N is the number of nodes in the binary tree. This is because each node is visited exactly once in a post-order traversal, and at each node, constant-time operations are performed.

The Space Complexity of this approach is O(1) Extra Space + O(H) Recursion Stack space (H is the height of the binary tree).

Before ending this article, let’s compare both the approaches:

Approach	Time complexity	Space complexity	Details
Brute force approach	O(N*N)	O(1)	Each node is visited multiple times to find the height of the left and right subtree for each node
Optimized approach	O(N)	O(1)	Each node is visited exactly once in a post-order traversal, and at each node, constant-time operations are performed.

By the way, there are many types of tree traversal available in programming.

Conclusion

In this article, we have discussed two approaches for checking for a balanced binary tree, which is very popular in leetcode as well. We have used the optimized approach using post-order traversal to solve this problem and implemented its code in C++, Java, and Python.