# [Leetcode 94] Binary Tree Inorder Traversal

Description:

Given the `root` of a binary tree, return the inorder traversal of its nodes' values.

Example 1:

`Input: root = [1,null,2,3]Output: [1,3,2]`

Example 2:

`Input: root = []Output: []`

Example 3:

`Input: root = [1]Output: [1]`

Example 4:

`Input: root = [1,2]Output: [2,1]`

Example 5:

`Input: root = [1,null,2]Output: [1,2]`

Constraints:

• The number of nodes in the tree is in the range `[0, 100]`.
• `-100 <= Node.val <= 100`

C code solution (recursive):

`/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     struct TreeNode *left; *     struct TreeNode *right; * }; *//** * Note: The returned array must be malloced, assume caller calls free(). */int* inorderTraversal(struct TreeNode* root, int* returnSize){    // boundary    if(!root){        *returnSize = 0;        return NULL;    }        //init    int *left_arr, *right_arr;    int left_size = 0, right_size = 0;        //main    //search left    if(root->left){        left_arr = inorderTraversal(root->left, &left_size);    }    //search right    if(root->right){        right_arr = inorderTraversal(root->right, &right_size);    }        // add up the size    *returnSize = 1 + left_size + right_size;        int *res = (int*)malloc((*returnSize) * sizeof(int));        // assign the elements    int res_idx = 0;    // assign left    for(int i=0; i<left_size; i++, res_idx++){        res[res_idx] = left_arr[i];    }    // assign current    res[res_idx++] = root->val;    //assign right    for(int i=0; i<right_size; i++, res_idx++){        res[res_idx] = right_arr[i];    }        return res;}`

Explanation:

C code solution (iterative):

`int* inorderTraversal(struct TreeNode* root, int* returnSize){    // boundary    if(!root){        *returnSize = 0;        return NULL;    }        //init    struct TreeNode* buffer[100];    int res_size = 0;    struct TreeNode* stack[100];    stack[0] = root;    int stack_size = 1;        //main    while(stack_size){        // curr points to the last position of stack        struct TreeNode* curr = stack[stack_size-1];        // search left to the end        while(curr->left){            // check if the left node has already in buffer            for(int i=0; i<res_size; i++){                if(buffer[i] == curr->left){                    goto LEFT_COMPLETE;                }            }            curr = curr->left;            stack[stack_size] = curr;            stack_size++;        }        LEFT_COMPLETE:        // pop the element from stack and place to buffer        curr = stack[stack_size-1];        stack[stack_size-1] = NULL;        stack_size--;        buffer[res_size] = curr;        res_size++;        //search one step to the right        if(curr->right){            stack[stack_size] = curr->right;            stack_size++;        }    }        // transfer the data from buffer to res    int *res = (int*)malloc(res_size * sizeof(int));    for(int i=0; i<res_size; i++)        res[i] = buffer[i]->val;    *returnSize = res_size;        return res;}`

Explanation:

Hi I am Samuel