#include <stdio.h>
#include <stdlib.h>

typedef struct cvor
{
    int broj;
    struct cvor *l, *d;
} cvor;

int max( int x, int y )
{
    return x < y ? y : x;
}

//додавање новог елемента у претраживачко стабло
void dodaj( cvor **koren, int x )
{
    if ( !*koren )
    {
        *koren = ( cvor * ) malloc( sizeof( cvor ) );
        ( *koren ) -> broj = x;
        ( *koren ) -> l = NULL;
        ( *koren ) -> d = NULL;
    }
    else if ( x < ( *koren ) -> broj ) dodaj( &( *koren ) -> l, x );
    else dodaj( &( *koren ) -> d, x );
}

//испис стабла у корен-леви-десни формату
void ispis( cvor *koren )
{
    if ( !koren ) return;
    printf("%d ", koren -> broj );
    ispis( koren -> l );
    ispis( koren -> d );
}

//2Д приказ стабла
void razmak( char c, int n )
{
    while ( n -- ) putchar( c );
}

void vizuelniPrikaz( cvor *koren, int nivo )
{
    if ( !koren )
    {
        razmak('\t', nivo );
        puts("~");
    }
    else
    {
        vizuelniPrikaz( koren -> d, nivo + 1 );
        razmak('\t', nivo );
        printf("%d\n", koren -> broj );
        vizuelniPrikaz( koren -> l, nivo + 1 );
    }
}

//проналажење највећег чвора у стаблу
int najveciCvor( cvor *koren ) // O(log n)
{
    if ( !koren ) return -1;
    if ( koren -> d ) return najveciCvor( koren -> d );
    return koren -> broj;
}

//итеративно проналажење највећег чвора у стаблу
int najveciCvorIter( cvor *koren ) // O(log n)
{
    if ( !koren ) return -1;

    while ( koren -> d ) koren = koren -> d;

    return koren -> broj;
}

//одређивање суме свих чворова у стаблу
int suma( cvor *koren ) // O(n)
{
    if ( !koren ) return 0;
    return koren -> broj + suma( koren -> l) + suma( koren -> d );
}

//одређивање дубине стабла
int dubina( cvor *koren ) // O(n)
{
    if ( !koren ) return 0;
    return max( dubina( koren -> l ), dubina( koren -> d ) ) + 1;
}

//да ли постоји чвор
int nadji( cvor *koren, int x ) // O(log n)
{
    if ( !koren ) return 0;
    if ( koren -> broj == x ) return 1;
    if ( x < koren -> broj ) return nadji( koren -> l, x );
    return nadji( koren -> d, x );
}

//на ком је нивоу чвор ако постоји
int nadjiNivo_( cvor *koren, int x, int nivo ) // O(log n)
{
    if ( !koren ) return -1;
    if ( koren -> broj == x ) return nivo;
    if ( x < koren -> broj ) return nadjiNivo_( koren -> l, x, nivo + 1 );
    return nadjiNivo_( koren -> d, x, nivo + 1 );
}

int nadjiNivo( cvor *koren, int x )
{
    return nadjiNivo_( koren, x, 0 );
}

int main()
{
    cvor *koren = NULL;

    int x;
    scanf("%d", &x );

    while ( x )
    {
        dodaj( &koren, x );
        scanf("%d", &x );
    }

    ispis( koren ); putchar('\n');

    vizuelniPrikaz( koren, 0 );
    printf("Najveci cvor je: %d\n", najveciCvor( koren ) );
    printf("Najveci cvor je: %d\n", najveciCvorIter( koren ) );
    printf("Suma svih cvorova je: %d\n", suma( koren ) );
    printf("Dubina stabla je: %d\n", dubina( koren ) );
    printf("Da li postoji %d: %s\n", 15, nadji( koren, 15 ) ? "da" : "ne" );
    printf("Na kom nivou je %d: %d\n", 15, nadjiNivo( koren, 15 ) );

    return 0;
}