Morris Traversal (hinglish) || O(1) space
IntuitionDekho bhailog,
BST ki property: Inorder traversal se nodes sorted order mein milti hain.
Example: 1, 2, 3, 4, 5
Agar k = 2 hai, toh iska matlab hai shu
# Intuition
Dekho bhailog,
BST ki property: Inorder traversal se nodes sorted order mein milti hain.
Example: 1, 2, 3, 4, 5
Agar k = 2 hai, toh iska matlab hai shuru se doosra element, yaani 2, return karna hai.

Process:
Inorder traversal se check karo aur har node visit karte hue k-- karo.
Jab k == 0 ho jaye, tab jo current node hai, woh k-th smallest hoga.
Solution:

Kth smallest nikalna hai toh inorder ka k-th smallest node return karna hai.
Space optimization ke liye Morris traversal ka use karo, jo BST ko bina extra space ke traverse karega.

Morris inorder traversal Samajna ho to : https://leetcode.com/problems/binary-tree-inorder-traversal/solutions/6298582/mentos-zindagi-morris-traversal-java
# Approach
Dry run krlo bhailog code ka

# Complexity
- Time complexity: O(N)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:O(1)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
       return morris(root, k);
    }

    public TreeNode getLeftRightMost(TreeNode node, TreeNode parent){
        while(node.right != null && node.right != parent){
            node = node.right;
        }
        return node;
    }
    public int morris(TreeNode root, int k){
        TreeNode curr = root;
        int res = -1;
        while(curr != null){
            TreeNode left = curr.left;
            if(left == null){
                k--;
                if(k == 0){
                    res = curr.val;
                    break;
                }
                curr = curr.right;
            }else{
                TreeNode leftRightMost = getLeftRightMost(curr.left, curr);
                if(leftRightMost.right == null){
                    leftRightMost.right = curr;
                    curr = curr.left;
                } else{
                    leftRightMost.right = null;
                     k--;
                   if(k == 0){
                    res = curr.val;
                    break;
                  }
                    curr = curr.right;
                }

            }
        }
        return res;
    }
}
```
['Java']