# C++ recursive & non-recursive solutions

• recursive solution

``````/**
* 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> result;

vector<int> inorderTraversal(TreeNode* root) {

dfs(root);
return result;
}
void dfs(TreeNode *root){
if(!root) return;
dfs(root->left);
result.push_back(root->val);
dfs(root->right);
}
};
``````

non-recursive solution

``````/**
* 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) {
stack<TreeNode*> stk;
vector<int> result;
TreeNode *p=root;

if(!root) return result;

while(p){
stk.push(p);
p=p->left;
}

while(!stk.empty()){
p=stk.top();
result.push_back(p->val);
stk.pop();

if(p->right){
p=p->right;
while(p){
stk.push(p);
p=p->left;
}
}

}
return result;
}

};
``````

• good solution!

// pseudocode
// p = root;
// while p is valid
// p = p -> left and store p
// then travel back,
// if the p->right is valid
// p = p -> left

class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> nodeStack;
vector<int> result;
TreeNode* p = root;
if(!root) return result; // edge case
// go to leftmost node first
while(p)
{
nodeStack.push(p); // push the node into stack
p = p->left;
}
// the search on the leftmost path is done
// and at this point, p point into a null pointer
// the next stage is too pop stack

``````while(!nodeStack.empty())  // while the stack is not emmpty
{
p = nodeStack.top();    // redirect p to point the top element
result.push_back(p->val); // push the value of the node
nodeStack.pop();          // pop the accessed node
// at this point, we need to check if there is right node adjacent to this ndoe
if(p->right) // if it is,we need to do a lefmost search
{
p = p->right;
while(p)  // do a lefmost search
{
nodeStack.push(p);
p = p->left;
}
}
}
``````

return result;
}

};

• list item

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