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");
}
}
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