Tuesday, 5 November 2019

Balanced Binary Tree

Given a binary tree, determine whether or not it is height-balanced. A height-balanced binary tree can be defined as one in which the heights of the two subtrees of any node never differ by more than one.

Algorithm:-

 import java.util.*;
class Node
{
    int data;
    Node left,right;
    Node(int data)
    {
        this.data=data;
        left=right=null;
    }
}
class CheckBT {
    Node root;
    boolean isBalanced(Node root)
    {
        if(root==null)
          return true;
        int l,r;
        l=height(root.left);
        r=height(root.right);
        if(Math.abs(l-r)<=1&&isBalanced(root.left)&&isBalanced(root.right))
             return true;      
      return false;       
    }
    int height(Node node)
    {
        if(node==null)
         return 0;
        return 1+Math.max(height(node.left),height(node.right));
    }
    public static void main (String[] args) {
        CheckBT tree=new CheckBT();
        tree.root=new Node(1);
        tree.root.left=new Node(2);
        tree.root.left.left=new Node(3);
        if(tree.isBalanced(tree.root))
           System.out.println("Balanced");
         else
           System.out.println("Not Balanced");
    }
}

No comments:

Post a Comment