morris traversal
\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0)
```\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\n\n//method1: inorder traversal\nclass Solution {\npublic:\n    void inorder(TreeNode* node,vector<int> &v){\n        if(node){\n            inorder(node->left,v);\n            v.push_back(node->val);\n            inorder(node->right,v);\n        }\n    }\n    \n    int kthSmallest(TreeNode* root, int k) {\n        vector<int> v;\n        inorder(root,v);\n        return v[k-1];\n    }\n};\n```\n\n//method2: using Morris Traversal\n```\nclass Solution {\npublic:\n    int kthSmallest(TreeNode* root, int k) {\n        TreeNode* curr=root,*pre;\n        int ans;\n        while(curr){\n            if(curr->left==NULL){\n                k--;\n                if(k==0) ans=curr->val;\n                curr=curr->right;\n            }else{\n                pre=curr->left;\n                while(pre->right && pre->right!=curr) pre=pre->right;\n                if(!pre->right){\n                    //this indicates we have pointer to the root element from where we should continue the traversing, so for inorder we jump to this root element,\n                    //& then traverse the right subtree from there.\n                    //to leave the tree as we found, set right element to the NULL again & jumps to root(the current root, parent of the current subtree) & continue.\n                    pre->right=curr;\n                    curr=curr->left;\n                }else{  //connecting rightmost element of the left subtree to current element, so we know where to continue when we finish with the \n                    //left subtree, basically to maintain inorder.\n                    //in inorder traversal after traversing all left elements root element should be traverse and then the rest of the right subtree elements.\n                    //so for that in morris traversal we connect rightmost element to the root(of current subtree).\n                    pre->right=NULL;\n                    k--;\n                    if(k==0) ans=curr->val;\n                    curr=curr->right;\n                }\n            }\n        }\n        return ans;\n    }\n};\n```
[]