C++ inorder traversal of binary tree

Question

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<int> inorderTraversal(TreeNode* root) {
 stack<TreeNode*> s; 
 vector<int> ans;
 if(root == nullptr) return ans; 
 s.push(root);
 while(!s.empty()){
 TreeNode* x = s.top();
 s.pop();
 if(x != nullptr && (x -> right != nullptr || x -> left != nullptr)){ 
 s.push(x -> right);
 s.push(x); 
 s.push(x -> left);
 }else{ //leaf node 
 if(x != nullptr)
 ans.push_back(x -> val);
 if(s.empty()) break;
 if(s.top() != nullptr)
 ans.push_back(s.top() -> val);
 s.pop();
 }
 }
 return ans;
 }

Answer 1

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.

• user172231: What do you mean by valid node? Do you mean non null?
• AJNeufeld: Yes. Exactly that. "If you are at a valid node ... otherwise (you have moved to a nullptr)"