I2R03. AVL trees P13827


Statement
 

pdf   zip

thehtml

Your task is to write a program that reads the shape of many general trees and, for each one, computes its height and decides if it is an AVL tree or not. We say that a tree is AVL if and only if

  • it has only one node;
  • or it has more than one node, all its children are AVL, and the difference between the heights of these children is at most one;

Input

The input starts with m, the number of trees that must be treated. The description of the m ‍trees follows as it is explained at the exercise of the collection, with two exceptions: the values are not given, because the contents of the nodes are not important here. The number of nodes is not given either, because it is not necessary to store the trees in any vector to solve this exercise.

Output

Your program must print one line for each tree of the input, with its height, and the indication of it is an AVL tree or not. Follow the format of the instance.

Public test cases
  • Input

    9
    
    1 0
    2 0 0
    1 1 0
    2 0 1 1 0
    2 1 1 1 0 2 1 1 0 0
    1 1 1 1 0
    3 0 0 0
    0
    3 1 1 0 0 1 0
    

    Output

    height 2, is avl
    height 2, is avl
    height 3, is avl
    height 4, is not avl
    height 5, is not avl
    height 5, is avl
    height 2, is avl
    height 1, is avl
    height 4, is not avl
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++