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

struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};

void padding ( char ch, int n )
{
  int i;
  for ( i = 0; i < n; i++ )
    putchar ( ch );
}

void structure ( struct TreeNode *root, int level )
{
  int i;
  if ( root == NULL ) {
    padding ( '\t', level );
    puts ( "~" );
  }
  else {
    structure ( root->right, level + 1 );
    padding ( '\t', level );
    printf ( "%d\n", root->data );
    structure ( root->left, level + 1 );
  }
}

struct TreeNode* createNode(int value) {
    struct TreeNode *node = (struct TreeNode*)malloc(sizeof(struct TreeNode));

    if(!node) {
        printf("Error\n");
        exit(1);
    }

    node -> data = value;
    node -> left = node -> right = NULL;

    return node;
}

void insert(struct TreeNode **root, int value) {
    struct TreeNode *newNode = createNode(value);

    if(*root == NULL) {
        *root = newNode;
        return;
    }

    struct TreeNode *pom = *root;
    struct TreeNode *prev = NULL;

    while (pom) {
        prev = pom;
        if (value < pom -> data) pom = pom -> left;
        else pom = pom -> right;
    }

    if (value < prev -> data) prev -> left = newNode;
    else prev -> right = newNode;
}

void formTree(struct TreeNode **root) {
    int value;

    scanf("%d", &value);
    while (value) {
        insert(root, value);
        structure(*root, 0);
        printf("-----------------------------------\n");
        scanf("%d", &value);
    }
}

void printInorder(struct TreeNode *root) {
    if (!root) return;

    printInorder(root->left);
    printf("%d ", root -> data);
    printInorder(root->right);
}

void printPreorder(struct TreeNode *root) {
    if (!root) return;

    printf("%d ", root -> data);
    printPreorder(root->left);
    printPreorder(root->right);
}

void printPostOrder(struct TreeNode *root) {
    if (!root) return;

    printPostOrder(root->left);
    printPostOrder(root->right);
    printf("%d ", root -> data);
}

struct TreeNode* findMax(struct TreeNode *root) {
    if(root == NULL) return NULL;

    struct TreeNode *pom = root;
    while(pom -> right) pom = pom -> right;

    return pom;
}

int caluculateSum(struct TreeNode *root) {
    if(root == NULL) return 0;

    int leftSum = caluculateSum(root -> left);
    int rightSum = caluculateSum(root -> right);

    return root -> data + leftSum + rightSum;
}

int treeDepth(struct TreeNode *root) {
    if (root == NULL) return 0;

    int leftDepth = treeDepth(root -> left);
    int rightDepth = treeDepth(root -> right);

    return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

int findX(struct TreeNode *root, int target) {
    int depth = 0;
    struct TreeNode *pom = root;

    while(pom) {
        depth++;

        if (pom -> data == target) return depth;
        if (target < pom -> data) pom = pom -> left;
        else pom = pom -> right;
    }

    return -1;
}

int main() {

    struct TreeNode *root = NULL;

    formTree(&root);
    structure(root, 0);
    printf("----------------------\n");
    printPreorder(root);
    printf("\n");

    printInorder(root);
    printf("\n");

    printPostOrder(root);
    printf("\n");

    struct TreeNode *max1 = findMax(NULL);
    struct TreeNode *max2 = findMax(root);

    if (max1) {
        printf("Maksimum je %d\n", max1 -> data);
    }
    else {
        printf("NULL\n");
    }

    if (max2) {
        printf("Maksimum je %d\n", max2 -> data);
    }
    else {
        printf("NULL\n");
    }
    

    int treeSum = caluculateSum(root);
    printf("%d\n", treeSum);

    int depth = treeDepth(root);
    printf("%d\n", depth);
    
    int depth1 = findX(root, 12);
    printf("Element on depth %d\n", depth1);

    int depth2 = findX(root, 11);
    printf("Element on depth %d\n", depth2);

    return 0;
}