Binary Tree Inorder Traversal

Binary Tree Inorder TraversalAug 27 '12

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

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {     
        vector<int> inOrderVector;
        stack<TreeNode*> inOrderStack;
        TreeNode *runner=root;
        
        if (!root)
            return inOrderVector;  
        while (!inOrderStack.empty() || runner) {
            if (runner) {
                inOrderStack.push(runner);
                runner=runner->left;
            }
            else {
                runner=inOrderStack.top();
                inOrderStack.pop();
                inOrderVector.push_back(runner->val);
                runner=runner->right;
            }
        }  
        return inOrderVector;
    }
};