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

typedef struct BST
{
    int val;
    struct BST *left, *right;
} node;

void add(node **root, int val)
{
    if (*root == NULL)
    {
        node *newnode = (node *)malloc(sizeof(node));
        newnode->val = val;
        newnode->left = NULL;
        newnode->right = NULL;
        *root = newnode;
    }
    else
    {
        node *cur = *root;
        (cur->val > val) ? add(&cur->left, val) : 
            (cur->val < val) ? add(&cur->right, val)
                : printf("%d already present in tree\n", val);
    }
}

int search(node *root, int val) {
    if(root == NULL)
        return 0;
    if(root->val == val)
        return 1;
    return (val < root->val) ? search(root->left, val) :
        search(root->right, val);
}

int height(node *root)
{
    if (root == NULL)
        return 0;
    int left = height(root->left);
    int right = height(root->right);
    return (left > right) ? left + 1 : right + 1;
}

int print_t(node *tree, int is_left, int offset, int depth, char s[20][255])
{
    char b[20];
    int width = 5;

    if (!tree)
        return 0;

    sprintf(b, "(%03d)", tree->val);

    int left = print_t(tree->left, 1, offset, depth + 1, s);
    int right = print_t(tree->right, 0, offset + left + width, depth + 1, s);

    for (int i = 0; i < width; i++)
        s[depth][offset + left + i] = b[i];

    if (depth && is_left)
    {
        for (int i = 0; i < width + right; i++)
            s[depth - 1][offset + left + width / 2 + i] = '-';

        s[depth - 1][offset + left + width / 2] = '.';
    }
    else if (depth && !is_left)
    {
        for (int i = 0; i < left + width; i++)
            s[depth - 1][offset - width / 2 + i] = '-';

        s[depth - 1][offset + left + width / 2] = '.';
    }

    return left + width + right;
}

void print(node *tree)
{
    char s[20][255];
    for (int i = 0; i < 20; i++)
        sprintf(s[i], "%80s", " ");

    print_t(tree, 0, 0, 0, s);
    int h = height(tree);
    for (int i = 0; i < h; i++)
        printf("%s\n", s[i]);
}


// int main()
// {
//     node *root = NULL;
//     add(&root, 100);
//     add(&root, 500);
//     add(&root, 200);
//     add(&root, 600);
//     add(&root, 20);
//     add(&root, 30);
//     add(&root, 25);
//     add(&root, 10);
//     print(root);
// }

int main()
{
    node *root = NULL;
    int num;
    int ch;
    while (1)
    {
        printf("\n1.Insert\n2.Search\n3.Print\n0.Exit\nEnter choice : ");
        scanf("%d", &ch);
        switch (ch)
        {
            case 1:
                printf("\nEnter element: ");
                scanf("%d", &num);
                add(&root, num);
                printf("\n[+] Inserted\n");
                break;
            case 2:
                printf("\nEnter element: ");
                scanf("%d", &num);
                printf("%s", search(root, num) ? "[*] Found\n" : "[-] Not found\n");
                break;
            case 3:
                print(root);
                break;
            case 0:
                exit(0);
            default:
                printf("\nInvalid Input\n");
                break;
        }
    }
    return 0;
}