1.In-order Traversal

In means root in between.

In-order traversal is to traverse the left subtree first. Then visit the root. Finally, traverse the right subtree.

For binary search tree, we can retrieve all the data in sorted order using in-order traversal.

Iterative Method using stack

Steps: 1. Print a node 2. Add the address to stack 2. Move to left subtree 3. Move to right subtree

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        
        stack<TreeNode*> s;
        TreeNode *t = root;
        vector<int> v;
        
        while(t!=NULL ||!s.empty()){
            
            if(t!=NULL){
                s.push(t);
                t = t->left;
            }
            else{
                t = s.top();
                v.push_back(t->val);
                s.pop();
                t = t->right;
            }
        }
        
        return v;
    }
};

Recursive method

class Solution {
public:
    vector<int> v;
    void inorder(TreeNode *t){
        if(t==NULL){
            return;
        }
        
        inorder(t->left);
        v.push_back(t->val);
        inorder(t->right);
        
    }
    vector<int> inorderTraversal(TreeNode* root) {
        inorder(root) ;   
        return v;
    }
};