Binary Tree Inorder Traversal

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

Solution: Iterative

We use a stack to store the parent nodes. If node is not null, we push it to the stack, and move to the left child. If the left child is null, the top node in stack is the parent node. We process the node, and then move to the right child.

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    if(!root) return result;

    stack<TreeNode*> stack;
    TreeNode* curNode = root;
    while(!stack.empty() || curNode) {
        if(curNode) {
            stack.push(curNode);
            curNode = curNode->left;
        } else {
            TreeNode* node = stack.top();
            result.push_back(node->val);
            stack.pop();

            curNode = node->right;
        }
    }

    return result;
}

Solution: Recursive

void inorderTraversalUtil(TreeNode *root, vector<int> &result) {
    if(root == NULL) return;
    inorderTraversalUtil(root->left, result);
    result.push_back(root->val);
    inorderTraversalUtil(root->right, result);
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    inorderTraversalUtil(root, result);
    return result;
}