/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
#define MAX(a,b) ((a) > (b) ? a : b)

int getHeight(struct TreeNode* root);
void fillret(struct TreeNode* root, int h, int l, int r, char ***ret);

char*** printTree(struct TreeNode* root, int** columnSizes, int* returnSize) {

    int height = getHeight(root);
    int w = (1<<height) - 1;    // 2^h -1
    *returnSize = w;
    printf("th height is %d, the w is %d", height, w);
    char*** ret=(char***)malloc(sizeof(char**)*height);
    *returnSize=height;

    columnSizes[0]=(int*)malloc(sizeof(int)*height);
    for(int i=0;i<height;i++){
        columnSizes[0][i]=w;
        ret[i]=(char**)malloc(sizeof(char*)*w);
        for(int j=0;j<w;j++){
            ret[i][j]="";
        }
    }

    fillret(root, 0, 0, w-1, ret);
    return ret;
}


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

    return MAX(getHeight(root->left), getHeight(root->right)) + 1;
}

void fillret(struct TreeNode* root, int h, int l, int r, char ***ret)
{
   if(!root) return;

    int midlle = (l + r) / 2;
    fillret(root->left, h+1, l, midlle - 1, ret);
    ret[h][midlle] = (char *)malloc(sizeof(char) * 4);
    sprintf(ret[h][midlle], "%d", root->val);
    fillret(root->right, h+1, midlle + 1, r, ret);
}