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

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isUnivalTree(struct TreeNode *root) {
    int v = root->val;

    struct TreeNode *nodes[124] = {0};
    int size = 0;

    if ( root->left != NULL ) nodes[size++] = root->left;
    if ( root->right != NULL ) nodes[size++] = root->right;

    for ( int i = 0; i < size; ++i ) {
        struct TreeNode *r = nodes[i];
        if ( r->val != v ) { return false; }
        if ( r->left != NULL ) nodes[size++] = r->left;
        if ( r->right != NULL ) nodes[size++] = r->right;
    }

    return true;
}

char *
treenode_to_cstr(const struct TreeNode *root)
{
    char *data = 0;
    unsigned long cap = 1024;
    unsigned long size = 0;

    if ( root == NULL ) {
        char *data = calloc(4, sizeof(char));
        return memcpy(data, "nil", 3);
    }

    data = calloc(cap, sizeof(*data));

    // TreeNode(%d, R, R)
    data[size++] = 'T';
    data[size++] = 'r';
    data[size++] = 'e';
    data[size++] = 'e';
    data[size++] = 'N';
    data[size++] = 'o';
    data[size++] = 'd';
    data[size++] = 'e';
    data[size++] = '(';
    if ( root->val > 99 ) { data[size++] = ((root->val / 100) % 10) + '0'; }
    if ( root->val > 9 ) { data[size++] = ((root->val / 10) % 10) + '0'; }
    data[size++] = (root->val % 10) + '0';
    data[size++] = ',';
    data[size++] = ' ';

    char *l = treenode_to_cstr(root->left);
    unsigned long lsize = strlen(l);
    if ( size+lsize >= cap ) {
        while (size+lsize >= cap) cap *= 2;
        data = realloc(data, cap);
    }
    for ( unsigned int i = 0; i < lsize; ++i ) { data[size++] = l[i]; }
    free(l);
    data[size++] = ',';
    data[size++] = ' ';

    char *r = treenode_to_cstr(root->right);
    unsigned long rsize = strlen(r);
    if ( size+rsize >= cap ) {
        while (size+rsize >= cap) cap *= 2;
        data = realloc(data, cap);
    }
    for ( unsigned int i = 0; i < rsize; ++i ) { data[size++] = r[i]; }
    free(r);

    data[size++] = ')';
    return data;
}


void
r(struct TreeNode *root, bool exp)
{

    char *root_cstr = treenode_to_cstr(root);
    printf("isUnivalTree(%s) = %b | exp: %b\n", root_cstr, isUnivalTree(root), exp);
    free(root_cstr);
}

int
main(void)
{
    struct TreeNode t1ll = {1, NULL, NULL};
    struct TreeNode t1lr = {1, NULL, NULL};
    struct TreeNode t1l = {1, &t1ll, &t1lr};
    struct TreeNode t1rr = {1, NULL, NULL};
    struct TreeNode t1r = {1, NULL, &t1rr};
    struct TreeNode t1 = {1, &t1l, &t1r};
    r(&t1, true);

    struct TreeNode t2ll = {5, NULL, NULL};
    struct TreeNode t2lr = {2, NULL, NULL};
    struct TreeNode t2l = {2, &t2ll, &t2lr};
    struct TreeNode t2r = {2, NULL, NULL};
    struct TreeNode t2 = {2, &t2l, &t2r};
    r(&t2, false);

    return 0;
}