Diameter of the trees P51080


Statement
 

pdf   zip

html

Write a program that reads the shape of various non empty binary trees, and for each one prints its diameter. The diameter of a tree is the maximal number of nodes of any path inside the tree. (or zero, if the tree is empty).

Input

Input starts with m, the number of trees that your program must treat. Follow the description of the m trees as is explained at the exercise : “”, with two exceptions: All the values are 0, because the content of the nodes here is not important. The number of nodes is not given, because you do not need to store the trees in any vector to solve this exercise.

Output

Your program must print the diameter of each tree.

Public test cases

  • Input

    4

0 0 0 -1 0 -1 -1 0 -1 -1 0 0 -1 -1 0 0 -1 0 -1 -1 -1
0 -1 0 -1 0 -1 -1
0 0 0 -1 -1 -1 0 0 -1 -1 -1
0 0 0 0 -1 -1 -1 0 0 -1 -1 -1 -1

    Output

    8
3
5
5
    • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++