# LC94 Inorder Traversal of binary tree

Given a binary tree, return the inorder traversal of its nodes’ values.
In order traversal means visit the left, then the root, then the right.

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int>res;
recurTraverse(root, res);
return res;
}
void recurTraverse(TreeNode* root, vector<int>& res){
if(root == NULL) return;
recurTraverse(root -> left, res);
res.push_back(root -> val);
recurTraverse(root -> right, res);
}
};
``````

# Iterative solution

In this code, we will use a stack to keep track of parent nodes.
We will first put root and all its left child node push onto the stack. And once we finished pushing all left child, we will pop the stack, store its value to res. Then if the poped node has right child, in the next iteration, we will push it and all its left child onto the stack. This method will ensure left-middle-right order.

``````    vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> parentStack;
vector<int> res;
TreeNode* currNode = root;
while(!parentStack.empty() || currNode){
if(currNode){
parentStack.push(currNode);
currNode = currNode -> left;
}
else{
TreeNode* tempNode = parentStack.top();
parentStack.pop();
res.push_back(tempNode -> val);
currNode = tempNode -> right;
}
}
return res;
}
``````
Posted on Categories Leetcode