# C++ solution using stack with explanation

• ``````/**
* 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> result;
if(root == NULL) {
return result;
}

vector<TreeNode*> nodeStack;
TreeNode* node = root;

nodeStack.push_back(node);
node = node->left;

while(!nodeStack.empty() || node != NULL) {
//walk through left child node at first
if(node != NULL) {
nodeStack.push_back(node);
node = node->left;
}
else {
//if there is no left child anymore, pop up current top node and add it to result
node = nodeStack.back();
nodeStack.pop_back();
result.push_back(node->val);

//if node stack is not empty, and there is no right child for current node, then continue
// to pop up the nodes from stack
//otherwise, walk though right child of current node
if(!nodeStack.empty()) {
if(node->right != NULL) {
node = node->right;
}
else {
node = NULL;
}
}
else {
node = node->right;
}
}
}

return result;
}
};``````

• ``````/*I optimized your  code,it get accepted*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root)
{
vector<int> result;
if(root == NULL)
return result;
vector<TreeNode*> nodeStack;
TreeNode* node = root;
nodeStack.push_back(node);
node = node->left;
while(!nodeStack.empty() || node != NULL)
{//walk through left child node at first
if(node != NULL)
{
nodeStack.push_back(node);
node = node->left;
}
else
{//if there is no left child anymore, pop up current top node and add it to result
node = nodeStack.back();
nodeStack.pop_back();
result.push_back(node->val);
node = node->right;
}
}
return result;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.