Find whether if a Given Binary Tree is Balanced?

Objective: Given a binary tree, Find whether if a Given Binary Tree is Balanced?

What is balanced Tree: A balanced tree is a tree in which difference between heights of sub-trees of any node in the tree is not greater than one.

Input: A Binary Tree

Output: True and false based on whether tree is balanced or not.

Example:

Balanced Tree Example

Approach :

Naive Approach:
for each node of the tree, get the height of left subtree and right subtree and check the difference , if it is greater than 1, return false.

Complete Code:

public class BalancedTree {
public static int getHeight(Node root){
if(root==null)return 0;
return (1+ Math.max(getHeight(root.left), getHeight(root.right)));
}
public static boolean isBalancedNaive(Node root){
if(root==null)return true;
int heightdifference = getHeight(root.left)getHeight(root.right);
if(Math.abs(heightdifference)>1){
return false;
}else{
return isBalancedNaive(root.left) && isBalancedNaive(root.right);
}
}
public static void main(String args[]){
Node root = new Node(5);
root.left = new Node(10);
root.right = new Node(15);
root.left.left = new Node(20);
root.left.right = new Node(25);
root.right.left = new Node(30);
root.right.right = new Node(35);
System.out.println(" Is Tree Balanced : " + (new BalancedTree()).isBalancedNaive(root));
root.right.right.right = new Node (40);
root.right.right.right.right = new Node (45);
System.out.println(" Is Tree Balanced : " + (new BalancedTree()).isBalancedNaive(root));
}
}
class Node{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
this.left = null;
this.right =null;
}
}

view raw
BalancedTree.java
hosted with ❤ by GitHub

Better Solution:

  • Recursion
  • Post order traversal technique
  • Travel all the way down to leaf nodes and then go up.
  • while going up, calculate the left and right subtree height.
  • If the difference between them is greater than 1, return -1.
  • Else Max(leftHeight, rightHeight) +1 .
  • Here you wont actually calculate the height of the subtrees by calling function, instead you will store the height at each level and when you go one level up, you add one to it.
  • So Time complexity is not O(N^2) but it will ne only O(N) but it will have space complexity as O(h) where h is the height of the treeBalanced Tree Example -1
    Complete Code:

    public class BalancedTree {
    public boolean checkBalance(Node root){
    int result = isBalanced(root);
    if(result>0){
    return true;
    }else{
    return false;
    }
    }
    public int isBalanced(Node root){
    if(root==null){
    return 0;
    }
    int leftH = isBalanced(root.left);
    if(leftH==1){
    return 1;
    }
    int rightH = isBalanced(root.right);
    if(rightH==1){
    return 1;
    }
    int diff = leftHrightH;
    if(Math.abs(diff)>1){
    return 1;
    }
    return 1 + Math.max(leftH, rightH);
    }
    public static void main(String args[]){
    Node root = new Node(5);
    root.left = new Node(10);
    root.right = new Node(15);
    root.left.left = new Node(20);
    root.left.right = new Node(25);
    root.right.left = new Node(30);
    root.right.right = new Node(35);
    System.out.println(" Is Tree Balanced : " + (new BalancedTree()).checkBalance(root));
    root.right.right.right = new Node (40);
    root.right.right.right.right = new Node (45);
    System.out.println(" Is Tree Balanced : " + (new BalancedTree()).checkBalance(root));
    }
    }
    class Node{
    int data;
    Node left;
    Node right;
    public Node(int data){
    this.data = data;
    this.left = null;
    this.right =null;
    }
    }

    view raw
    BalancedTree.java
    hosted with ❤ by GitHub

    Output:

    Is Tree Balanced : true
    Is Tree Balanced : false