Recursion

-time complexity: O(n) ( recurrrence relation: T(n) = 2*T(n/2)+1 )
-space complexity: O(h) (where h is the height of the tree)
why? At most n activation records are on the stack at one point (in the worst case)

Iteration: using stack

-time complexity: O(n)
-space complexity: O(n)

Morris Traversal

-time complexity: O(n)
-space complexity: O(1)

code from here

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    TreeNode* cur = root;
    TreeNode* pre;

    while(cur!=nullptr){
        //search for leftmost node in the subtree
        if(cur->left!=nullptr){
            pre = cur->left;
            while((pre->right!=nullptr) && (pre->right!=cur))
                pre = pre->right;
            //predecessor of cur node is pre
            if(pre->right==nullptr){
                pre->right = cur;
                cur = cur->left;
            }
            //break the chain and traverse right subtree
            else{
                pre->right = nullptr;
                ans.push_back(cur->val);
                cur = cur->right;
            }
        }
        //leftmost node in the subtree
        else{
            ans.push_back(cur->val);
            cur = cur->right;
        }
    }

    return ans;
}