# A recursive and an iterative solution both accepted with 0ms in C enclosed with a MorrisTraversal solution!

• ``````void traverse(struct TreeNode* root, int** arr, int* returnSize)
{
*returnSize += 1;
*arr = (int*)realloc(*arr, sizeof(int)*(*returnSize));
(*arr)[*returnSize-1] = root->val;
if(root->left)
traverse(root->left, arr, returnSize);
if(root->right)
traverse(root->right, arr, returnSize);
}
//AC - 0ms;
int* preorderTraversal0(struct TreeNode* root, int* returnSize)
{
if(!root) return NULL;
int* arr = (int*)malloc(sizeof(int));
*returnSize = 0;
traverse(root, &arr, returnSize);
return arr;
}

void storeAndCollectLeftNodes(struct TreeNode* root, struct TreeNode*** stack, int* size, int** arr, int* returnSize)
{
while(root)
{
*returnSize += 1;
*arr = (int*)realloc(*arr, sizeof(int)*(*returnSize));
(*arr)[*returnSize-1] = root->val;
*stack = (struct TreeNode**)realloc(*stack, sizeof(struct TreeNode*)*(*size+1));
*size += 1;
(*stack)[*size-1] = root;
root = root->left;
}
}

//AC - 0ms;
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
if(!root) return NULL;
int* arr = (int*)malloc(sizeof(int));
*returnSize = 0;
struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
int size = 0;
storeAndCollectLeftNodes(root, &stack, &size, &arr, returnSize);
while(size)
{
root = stack[size-1];
size--;
if(root->right) //handle the right children of leftmost nodes;
storeAndCollectLeftNodes(root->right, &stack, &size, &arr, returnSize);
}
return arr;
}

//AC - 0ms - MorrisTraversal;
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
if(!root) return NULL;
int* arr = (int*)malloc(sizeof(int));
*returnSize = 0;
while(root)
{
if(!root->left)
{
*returnSize += 1;
arr = (int*)realloc(arr, sizeof(int)*(*returnSize));
arr[*returnSize-1] = root->val;
root = root->right;
}
else
{
struct TreeNode* pre = root->left;
while(pre->right && pre->right!=root)
pre = pre->right;
if(!pre->right)
{
*returnSize += 1;
arr = (int*)realloc(arr, sizeof(int)*(*returnSize));
arr[*returnSize-1] = root->val;
pre->right = root;
root = root->left;
}
else
{
pre->right = NULL;
root = root->right;
}
}
}
return arr;
}``````

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