Check if Binary Tree is Balanced in DSA Java - Build from Scratch

Check if Binary Tree is Balanced

📖 Scenario: Imagine you are building a system that manages a family tree. To keep the tree efficient for searching, you want to check if the tree is balanced. A balanced tree means the left and right branches of every node do not differ in height by more than one.

🎯 Goal: You will create a simple binary tree, write a method to check if it is balanced, and print the result.

📋 What You'll Learn

Create a binary tree with specific nodes

Add a helper method to calculate height

Write a method to check if the tree is balanced

Print the boolean result of the balance check

💡 Why This Matters

🌍 Real World

Balanced binary trees are used in databases and file systems to keep data organized for fast searching and updating.

💼 Career

Understanding tree balance is important for software engineers working on performance-critical applications and data structure optimization.

1

Create the Binary Tree Structure

Create a class called TreeNode with an integer val, and two TreeNode references called left and right. Then create a binary tree with root node value 1, left child value 2, and right child value 3. The left child of node 2 should be 4, and the right child of node 2 should be 5. The right child of node 3 should be 6.

DSA Java

// Define TreeNode class and create the binary tree
// Your code here

Hint

Start by defining the TreeNode class with the required fields and constructor. Then create the nodes and link them as described.

2

Add a Helper Method to Calculate Height

Inside the Main class, add a static method called height that takes a TreeNode parameter called node and returns an int. This method should return 0 if node is null. Otherwise, it should return 1 + Math.max(height(node.left), height(node.right)).

DSA Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
    }

    // Add the height method below
    // Your code here
}

Hint

The height of a node is 1 plus the maximum height of its left and right children. If the node is null, height is 0.

3

Write the Method to Check if the Tree is Balanced

Inside the Main class, add a static method called isBalanced that takes a TreeNode parameter called node and returns a boolean. This method should return true if node is null. Otherwise, it should check if the absolute difference between the height of node.left and node.right is less than or equal to 1, and recursively check if node.left and node.right are balanced. Return true only if all these conditions hold.

DSA Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
    }

    public static int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }

    // Add the isBalanced method below
    // Your code here
}

Hint

Check the height difference between left and right children. If difference is more than 1, return false. Otherwise, check recursively for left and right subtrees.

4

Print the Result of the Balance Check

In the main method, after creating the tree, add a line to print the result of calling isBalanced(root).

DSA Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        // Print the result of isBalanced(root) below
        // Your code here
    }

    public static int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }

    public static boolean isBalanced(TreeNode node) {
        if (node == null) {
            return true;
        }
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return false;
        }
        return isBalanced(node.left) && isBalanced(node.right);
    }
}

Hint

Use System.out.println(isBalanced(root)); to print the result.

Practice

1. What does it mean for a binary tree to be balanced?

easy

A. The height difference between left and right subtrees of every node is at most 1

B. All nodes have two children

C. The tree has the same number of nodes on left and right

D. The tree is a complete binary tree

Solution

1. Step 1: Understand balance condition

   A balanced binary tree means the height difference between left and right subtrees of every node is at most 1.

2. Step 2: Compare other options

   Options A, B, and C describe different tree properties but not the balance condition.

3. Final Answer:

   The height difference between left and right subtrees of every node is at most 1 -> Option A

4. Quick Check:

   Balance means height difference ≤ 1 [OK]

Hint: Balance means height difference ≤ 1 at every node [OK]

Common Mistakes:

• Confusing balanced with complete tree
• Thinking balance means equal number of nodes
• Assuming all nodes must have two children

2. Which Java method signature correctly defines a function to check if a binary tree is balanced?

easy

A. boolean isBalanced(TreeNode root) void

B. public boolean isBalanced(TreeNode root)

C. public void isBalanced(TreeNode root) returns boolean

D. boolean isBalanced(TreeNode root) public

Solution

1. Step 1: Check Java method syntax

   Correct Java method signature includes access modifier, return type, method name, and parameters: public boolean isBalanced(TreeNode root)

2. Step 2: Identify incorrect syntax

   Options A, C, and D have invalid order or keywords not used in Java method declarations.

3. Final Answer:

   public boolean isBalanced(TreeNode root) -> Option B

4. Quick Check:

   Java method syntax: access returnType name(params) [OK]

Hint: Java method: access modifier + return type + name + parameters [OK]

Common Mistakes:

• Mixing return type and void
• Wrong keyword order
• Missing access modifier

3. What will be the output of the following code snippet?

class TreeNode {
  int val;
  TreeNode left, right;
  TreeNode(int x) { val = x; }
}

public class Solution {
  public boolean isBalanced(TreeNode root) {
    if (root == null) return true;
    int leftHeight = height(root.left);
    int rightHeight = height(root.right);
    if (Math.abs(leftHeight - rightHeight) > 1) return false;
    return isBalanced(root.left) && isBalanced(root.right);
  }

  private int height(TreeNode node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.left.left.left = new TreeNode(5);
    Solution sol = new Solution();
    System.out.println(sol.isBalanced(root));
  }
}

medium

A. false

B. true

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Calculate subtree heights

   Left subtree of root has height 3 (nodes 2 -> 4 -> 5), right subtree has height 1 (node 3). Difference is 2 > 1.

2. Step 2: Check balance condition

   Since height difference > 1 at root, isBalanced returns false.

3. Final Answer:

   false -> Option A

4. Quick Check:

   Height difference > 1 means unbalanced = false [OK]

Hint: Check height difference at root first for quick balance check [OK]

Common Mistakes:

• Ignoring height difference > 1
• Assuming tree is balanced by default
• Confusing height with node count

4. Identify the bug in this code snippet that checks if a binary tree is balanced:

public boolean isBalanced(TreeNode root) {
  if (root == null) return true;
  int leftHeight = height(root.left);
  int rightHeight = height(root.right);
  if (Math.abs(leftHeight - rightHeight) > 1) return false;
  return isBalanced(root.left) || isBalanced(root.right);
}

private int height(TreeNode node) {
  if (node == null) return 0;
  return 1 + Math.max(height(node.left), height(node.right));
}

medium

A. Incorrect height calculation formula

B. Missing base case for null root

C. Using || instead of && in recursive call

D. No return statement in height method

Solution

1. Step 1: Analyze recursive calls

   The code uses || (OR) to combine left and right subtree balance checks, which returns true if either subtree is balanced.

2. Step 2: Correct logic for balance

   Both left and right subtrees must be balanced, so && (AND) should be used instead of ||.

3. Final Answer:

   Using || instead of && in recursive call -> Option C

4. Quick Check:

   Balance requires both subtrees balanced: use && [OK]

Hint: Use && to ensure both subtrees are balanced [OK]

Common Mistakes:

• Using || instead of &&
• Forgetting base case
• Miscomputing height

5. Given a binary tree, how can you optimize the balance check to avoid repeated height calculations?

hard

A. Use a queue to traverse nodes level by level

B. Calculate height separately for left and right subtrees multiple times

C. Only check balance at the root node

D. Calculate height and balance in one recursive function returning a special value

Solution

1. Step 1: Identify inefficiency in naive approach

   Naive method calculates height repeatedly for subtrees, causing extra work.

2. Step 2: Use combined recursive function

   Return height if subtree is balanced, else return -1 to indicate imbalance, avoiding repeated height calls.

3. Final Answer:

   Calculate height and balance in one recursive function returning a special value -> Option D

4. Quick Check:

   Combine height and balance check to optimize [OK]

Hint: Return -1 on imbalance to stop early and save time [OK]

Common Mistakes:

• Recalculating height multiple times
• Using level order traversal which doesn't help balance check
• Checking balance only at root