C++ inorder traversal of binary tree The challenge was to create a function which performs an in order traversal without using recursion. What I came up with was to use a stack and some clever popping and pushing. I was wondering if there was any way to improve the following solution. Specifically a better way to implement my if(s.empty()) break; line.

vector&lt;int&gt; inorderTraversal(TreeNode* root) {
        stack&lt;TreeNode*&gt; s; 
        vector&lt;int&gt; ans;
        if(root == nullptr) return ans; 
        s.push(root);
        while(!s.empty()){
            TreeNode* x = s.top();
            s.pop();
            if(x != nullptr &amp;&amp; (x -&gt; right != nullptr || x -&gt; left != nullptr)){        
                s.push(x -&gt; right);
                s.push(x); 
                s.push(x -&gt; left);
            }else{ //leaf node 
                if(x != nullptr)
                    ans.push_back(x -&gt; val);

                if(s.empty()) break;

                if(s.top() != nullptr)
                    ans.push_back(s.top() -&gt; val);
                s.pop();
            }
        }
        return ans;
    }
Your algorithm does seem to work, but it is very complex.  You are pushing nullptr onto the stack when a node has only one child, so you have to check for x != nullptr (which you do),   and if the top of the stack is nullptr (which again, you do).

A better approach would be:


start with an empty vector
start with an empty stack
start with root as the current node
while you are at a valid node, or if the stack is not empty:


if you are at a valid node:


if it has a left child,


push the current node onto the stack
move to the left child.

otherwise (it doesn't have a left child)


append its value to your vector
move to the right child (even if it doesn't exist)


otherwise (you have moved to a nullptr):


pop a node from the stack
append its value to your vector
move to the right child (even if it doesn't exist)




Notice you never push a nullptr onto the stack.  You never need to push a node onto the stack unless you need to return to it.  When you do return to it, you immediately process it by appending its value and moving to its right child.

Also notice that an empty tree is no longer a special case.