# C solution using DFS and postfix traversal (not reverse)

• Compare to `Binary Tree Level Order Traversal` which was resovled using prefix traversal, this just the postfix case.

(My solution of `Binary Tree Level Order Traversal`: https://discuss.leetcode.com/topic/59106/c-solution-using-dfs)

But, if want to using postfix traversal, we need to know the max depth in advance, so it seems that I have to do an extra traversal to get the max depth

``````/**
* 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().
*/

void traverse(struct TreeNode *root, int depth, int ***arr, int **columnSizes, int *returnSize)
{
int     idx;

if (!root) return;

traverse(root->left, depth + 1, arr, columnSizes, returnSize);
traverse(root->right, depth + 1, arr, columnSizes, returnSize);

idx = *returnSize - depth - 1;
(*arr)[idx] = realloc((*arr)[idx], ((*columnSizes)[idx] + 1) * sizeof(int));
(*arr)[idx][(*columnSizes)[idx]] = root->val;
++(*columnSizes)[idx];
}

void maxdepth(struct TreeNode *root, int depth, int ***arr, int **columnSizes, int *returnSize)
{
if (!root) return;

if (*returnSize < depth + 1) {
*returnSize = depth + 1;

/*
* Should initialise the one more allocated space to NULL (or 0)
*/
*arr = realloc(*arr, (depth + 1) * sizeof(int *));
(*arr)[depth] = NULL;

*columnSizes = realloc(*columnSizes, (depth + 1) * sizeof(int));
(*columnSizes)[depth] = 0;
}

maxdepth(root->left, depth + 1, arr, columnSizes, returnSize);
maxdepth(root->right, depth + 1, arr, columnSizes, returnSize);
}

int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize) {
int **arr;

arr = NULL;
*returnSize = 0;
maxdepth(root, 0, &arr, columnSizes, returnSize);
traverse(root, 0, &arr, columnSizes, returnSize);

return arr;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.