Determining if a Binary Tree is Balanced in Java

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

A binary tree is considered balanced if the depth of its two subtrees for any given node never differs by more than one. In this blog post, we'll dive into a Java program that checks if a binary tree is balanced. We'll walk you through the entire process, from understanding the core logic to implementing the code and interpreting the output. 

Understanding the Logic 

Before we dive into the code, let's first understand the logic. For every node: 

1. Calculate the height of the left and right subtrees. 
2. If the difference in heights is more than 1, or if any of the subtrees is unbalanced, the tree is not balanced. 

Program Implementation

// Define the node structure
class TreeNode {
    int value;
    TreeNode left, right;

    TreeNode(int item) {
        value = item;
        left = right = null;
    }
}

public class BinaryTree {
    
    TreeNode root;  // Root of the binary tree

    // Utility function to determine the height of the tree
    public int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }

    // Function to check if the tree is balanced
    public boolean isBalanced(TreeNode node) {
        if (node == null) {
            return true;  // Base case
        }
        
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);

        return (Math.abs(leftHeight - rightHeight) <= 1) && 
               isBalanced(node.left) && 
               isBalanced(node.right);
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        
        // Create nodes of the tree
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(5);
        tree.root.left.left.left = new TreeNode(8);

        if (tree.isBalanced(tree.root)) {
            System.out.println("The tree is balanced");
        } else {
            System.out.println("The tree is not balanced");
        }
    }
}

Output:

The tree is not balanced

Step-by-step Explanation: 

TreeNode Class: 

• This defines the structure of a node in our binary tree. Each node contains a value and pointers to its left and right child nodes. 

height Method:

• It's a helper method that computes the height of the tree recursively. 
• If the node is null, the height is zero. Otherwise, the height is 1 (for the current node) plus the maximum of the heights of the left and right children. 

isBalanced Method: 

• This method is the core of our program. It checks if a binary tree is balanced. 
• For each node, it calculates the heights of the left and right subtrees. If the difference is more than 1, or if any of the subtrees is not balanced, it returns false. 
• If the tree passes these checks for all nodes, the method returns true, indicating the tree is balanced.

main Method: 

• We instantiate the BinaryTree class and create a sample binary tree. 
• We then call the isBalanced method on the root of the tree and print out the result. 

In the given sample tree, the left subtree has a height of 3 (from root to the deepest node 8), while the right subtree has a height of just 1. Since the difference is 2 (which is greater than 1), the program correctly determines that the tree is not balanced.

My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:

Build REST APIs with Spring Boot 4, Spring Security 7, and JWT

🆕 High-Demand 80–90% OFF

[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25

🆕 High-Demand 80–90% OFF

ChatGPT + Generative AI + Prompt Engineering for Beginners

🚀 Trending Now 80–90% OFF

Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Real-Time REST APIs with Spring Boot - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Microservices with Spring Boot and Spring Cloud

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Java Full-Stack Developer Course with Spring Boot and React JS

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Build 5 Spring Boot Projects with Java: Line-by-Line Coding

🌟 Top Rated 80–90% OFF

Testing Spring Boot Application with JUnit and Mockito

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot Thymeleaf Real-Time Web Application - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Master Spring Data JPA with Hibernate

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot + Apache Kafka Course - The Practical Guide

🎓 Student Favorite 80–90% OFF
Available in Udemy for Business

Java Testing: Mastering JUnit 5 Framework

🆕 New 80–90% OFF

Reactive Programming in Java: Spring WebFlux and Testing

🌟 Top Rated 80–90% OFF

Spring Boot + RabbitMQ Course - The Practical Guide

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Functional Programming in Java (Includes Java Collections)

🎓 Student Favorite 80–90% OFF

ChatGPT for Java Developers: Boost Your Productivity with AI

🚀 Trending Now 80–90% OFF