/* inorder traversal binary tree */

 #include <stdio.h>

 #include <stdlib.h>

 struct TreeNode {

     int val;

     struct TreeNode *left;

     struct TreeNode *right;

 };

 int* inorderTraversal(struct TreeNode* root, int* returnSize);

 int main() {

     struct TreeNode n1, n2, n3;

     n1.val = 1;

     n1.left = NULL;

     n1.right = &n2;

     /*  */

     n2.val = 2;

     n2.left = &n3;

     n2.right = NULL;

     /*  */

     n3.val = 3;

     n3.left = NULL;

     n3.right = NULL;

     int returnSize = 0;

     int *a = inorderTraversal(&n1, &returnSize);

     int i=0;

     for(i=0; i<returnSize; i++)

         printf("%d ", a[i]);

     printf("\n");

 }

 /**

  * Definition for a binary tree node.

  * struct TreeNode {

  *     int val;

  *     struct TreeNode *left;

  *     struct TreeNode *right;

  * };

  */

 /**

  * Return an array of size *returnSize.

  * Note: The returned array must be malloced, assume caller calls free().

  */

 int* inorderTraversal(struct TreeNode* root, int* returnSize) {

     struct TreeNode  **stack = (struct TreeNode **) malloc (sizeof(struct TreeNode *) * 1000); /* store node not access at present */

     int *result = (int *) malloc(sizeof(int) * 1000);

     int count = 0;

     stack[0] = root;           /* first node */

     struct TreeNode* curr;

     int top = 0;                /* element number in stack */

     while(top != -1 ) {

         curr = stack[top];    /* get stack top element */

         if(curr == NULL) {     /* if current element is null */

             while(top != -1 && curr == NULL)

                 curr = stack[--top];

             if(top == -1 || curr == NULL)

                 break;

             else {

                 result[count++] = curr->val;

                 stack[top] = curr->right;

                 continue;

             }

         }

         if(curr->left != NULL)

             stack[++top] = curr->left;

         if(curr->left == NULL) {  /* if left subtree is NULL, then we need to access middle node */

             result[count++] = curr->val;

             stack[top] = curr->right;

         }

     }

     *returnSize = count;

     return result;

 }