Question

AVL trees in Java

For a given adjacency matrix of a rooted tree you need to decide whether this tree can be labeled to become an avl tree.

Vertices of the tree do not have keys but numbered from 0 to n − 1 in order to write the adjacency matrix.

INPUT format: The input consists of blocks. Blocks are written one after another without empty lines between them. Every block starts with a new line and consists of several lines:

• the first line contains a positive integer number n which corresponds to the number of nodes in a tree and the root index;

• the next n lines correspond to the adjacency matrix of this tree.

OUTPUT format: The answer for every block should consist of the height of the tree and True/False (True if the tree is an avl tree).

Answers for different blocks should be located in different lines.

Input example:

5 3
0 0 0 0 0
1 0 1 0 0
0 0 0 0 0
0 1 0 0 1
0 0 0 0 0
4 0
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0
10 3
0 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
10 6
0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0

Output example:

2 True
3 False
3 True
4 False

please make comments for code

Answer 1

Java code for above problem

import java.util.*;

// class for a node in tree
class Node
{
   int data;
   Node left,right;
   Node(int data)
   {
       this.data=data;
       this.left=null;
       this.right=null;
   }
}
class Main
{
   // global variable to say that given tree is AVL or not
   public static boolean isAVL=true;
  
   // testing main method
   public static void main(String args[])
   {
       Scanner file=new Scanner(System.in);
       int n=file.nextInt();
       int start=file.nextInt();
       int [][] graph=new int[n][n];
       for(int i=0;i<n;i++)
       {
           for(int j=0;j<n;j++)
           {
               graph[i][j]=file.nextInt();
           }
       }
       Node root=create_graph(graph,n,start);
       System.out.println(height(root)+" "+(isAVL(root) ? "True" : "False"));
   }
  
   // method that returns the height of tree of given root node
   public static int height(Node root)
   {
       if(root==null || (root.left==null && root.right==null))
           return 0;
       int leftHeight=height(root.left);
       int rightHeight=height(root.right);
       return 1+Math.max(leftHeight,rightHeight);
   }
  
   // method that returns whether the tree with given root is AVL or not
   public static boolean isAVL(Node root)
   {
       isAVL=true;
       checkForAVL(root);
       return isAVL;
   }
  
   // helper method for isAVL() method
   public static int checkForAVL(Node root)
   {
       if(root==null || (root.left==null && root.right==null))
           return 0;
       int leftHeight=checkForAVL(root.left);
       int rightHeight=checkForAVL(root.right);
       if(Math.abs(leftHeight-rightHeight)>1)
           isAVL=false;
       return 1+Math.max(leftHeight,rightHeight);
   }
  
   // method that creates a tree of given graph
   public static Node create_graph(int graph[][],int n,int index)
   {
       Node node=new Node(index);
       for(int i=0;i<n;i++)
       {
           if(graph[index][i]==1)
           {
               if(node.left==null)
               {
                   node.left=create_graph(graph,n,i);
               }
               else
               {
                   node.right=create_graph(graph,n,i);
               }
           }
       }
       return node;
   }
}

Sample output

Mention in comments if any mistakes or errors are found. Thank you.