Answer to Question #204363 in Java | JSP | JSF for Fatima Jabeen

Question

Design a method that determines whether or not a binary tree is fully balanced. This method takes no parameters, and returns a boolean value: true if the tree is fully balanced, and false if it is not.

Answer 1

The code below is a program that test whether a binary tree is fully balanced. The method isTree_Balanced() is the solution to the question asked. The whole program test the isTree_Balanced() method.

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package tree_fully_balanced;


/**
 *
 * @author Student
 */
class Tree_Node {
    int first;
    Tree_Node left_node, right_node;
   Tree_Node(int f)
    {
        first = f;
        left_node = right_node = null;
    }
}


 
public class Tree_fully_balanced {
    Tree_Node root;
 
   
    boolean isTree_Balanced(Tree_Node nod)
    {
        int left_height; 
 
        int right_height; 
 
        
        if (nod == null)
            return true;
 
       
        left_height = height_of_tree(nod.left_node);
        right_height = height_of_tree(nod.right_node);
 
        if (Math.abs(left_height - right_height) <= 1
            && isTree_Balanced(nod.left_node)
            && isTree_Balanced(nod.right_node))
            return true;
 
        
        return false;
    }
 
  // Finding a height of a tree
    int height_of_tree(Tree_Node nod)
    {
       
        if (nod == null)
            return 0;
 
        
        return 1 + Math.max(height_of_tree(nod.left_node), height_of_tree(nod.right_node));
    }
 


    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
         Tree_fully_balanced tr = new  Tree_fully_balanced();
        tr.root = new Tree_Node(1);
        tr.root.left_node = new Tree_Node(2);
        tr.root.right_node = new Tree_Node(3);
        tr.root.left_node.left_node = new Tree_Node(4);
        tr.root.left_node.right_node = new Tree_Node(5);
        tr.root.left_node.left_node.left_node = new Tree_Node(8);
 
        if (tr.isTree_Balanced(tr.root))
            System.out.println("Binary Tree Fully Balanced");
        else
            System.out.println("Binary Tree not balanced");
        
    }
    
}