0102-binary-tree-level-order-traversal.c

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 * int val;
 * struct TreeNode *left;
 * struct TreeNode *right;
 * };
 */

#defineARRAY_ALLOCATION_SIZE 500
typedefstructTreeNodeTreeNode;

// Circular queue with dynamic size
typedefstructQueue
{
TreeNode**treeNodeArray;
inttreeNodeArraySize; // Allocated size of the treeNodeArray
inttreeNodeArrayUsed; // Number of used space in the treeNodeArray
intfront;
intback;
}Queue;

voidqueueInit(Queue*queue)
{
queue->treeNodeArray= (TreeNode**)malloc(ARRAY_ALLOCATION_SIZE*sizeof(TreeNode*));
queue->treeNodeArraySize=ARRAY_ALLOCATION_SIZE;
queue->treeNodeArrayUsed=0;
queue->front=-1;
queue->back=-1;
}

intisQueueEmpty(Queue*queue)
{
if(queue->treeNodeArrayUsed==0)
 {
return true;
 }

return false;
}

voidqueuePush(Queue*queue, TreeNode*node)
{
// Check if space reallocation is needed
if(queue->treeNodeArrayUsed==queue->treeNodeArraySize)
 {
// Reallocate bigger space for the array
queue->treeNodeArraySize+=ARRAY_ALLOCATION_SIZE; // Increase the array size
queue->treeNodeArray= (TreeNode**)realloc(queue->treeNodeArray, queue->treeNodeArraySize*sizeof(TreeNode*));

// If the front passed the back, we need to move any element statring of the front to the end of the array
if(queue->front >= queue->back)
 {
intoldArraySize= (queue->treeNodeArraySize-ARRAY_ALLOCATION_SIZE);
// Calculate how many elements we need to move, starting from the from til the array end (with old array size before reallocation)
intelementsToMoveCount=oldArraySize-queue->front;

for(inti=1; i<elementsToMoveCount; i++)
 {
printf("%d, %d\n", i, elementsToMoveCount);
queue->treeNodeArray[queue->treeNodeArraySize-i] =queue->treeNodeArray[--oldArraySize];
 }

// Set the new front position
queue->front=queue->treeNodeArraySize-elementsToMoveCount;
 }
 }

// If back is at the end of the array, we circle back to beginning of the array
if(++queue->back==queue->treeNodeArraySize)
 {
queue->back=0;
 }

// Add node at the back
queue->treeNodeArray[queue->back] =node;

// Increment the treeNodeArrayUsed counter
queue->treeNodeArrayUsed++;
}

TreeNode*queuePop(Queue*queue)
{
// Make sure the queue is not empty
if(!isQueueEmpty(queue))
 {
// Decrement the treeNodeArrayUsed counter
queue->treeNodeArrayUsed--;

// If front is at the end of the array, we circle back to beginning of the array
if(++queue->front==queue->treeNodeArraySize)
 {
queue->front=0;
 }

returnqueue->treeNodeArray[queue->front];
 }

returnNULL;
}


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int**levelOrder(structTreeNode*root, int*returnSize, int**returnColumnSizes){
intresultAllocatedSize=ARRAY_ALLOCATION_SIZE;
int**result= (int**)malloc(resultAllocatedSize*sizeof(int*));
intresultIndex=0;
Queuequeue;

// Initialize to 0
*returnSize=0;
*returnColumnSizes= (int*)malloc(resultAllocatedSize*sizeof(int));


if(!root)
 {
returnresult;
 }

queueInit(&queue);
// Initialize the queue with the root node
queuePush(&queue, root);

while(!isQueueEmpty(&queue))
 {
intlevelLen=queue.treeNodeArrayUsed;
int*level= (int*)malloc(levelLen*sizeof(int));
intlevelIndex=0;

for(inti=0; i<levelLen; i++)
 {
TreeNode*poppedNode=queuePop(&queue);

level[levelIndex++] =poppedNode->val;
if(poppedNode->left)
 {
queuePush(&queue, poppedNode->left);
 }

if(poppedNode->right)
 {
queuePush(&queue, poppedNode->right);
 }
 }

// Check if result array has enough space
if(resultIndex+1==resultAllocatedSize)
 {
resultAllocatedSize+=ARRAY_ALLOCATION_SIZE;

result= (int**)realloc(result, resultAllocatedSize*sizeof(int*));
*returnColumnSizes= (int*)realloc(*returnColumnSizes, resultAllocatedSize*sizeof(int));
 }

result[resultIndex] =level;
 (*returnColumnSizes)[resultIndex] =levelLen;
resultIndex++;
 (*returnSize)++;
 }

returnresult;
}