# O(n) time O(1) space solution using Morris Inorder Traversal in Java

• ``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int kthSmallest(TreeNode root, int k) {
TreeNode kth = MorrisInorderTraversal(root, k);
return kth != null ? kth.val : -1;
}

public static TreeNode MorrisInorderTraversal(TreeNode root, int k){
if(root == null){
return null;
}

TreeNode cur = root;
TreeNode pre = null;
while(cur != null){
//if no left subtree the visit right subtree right away after printing current node
if(cur.left == null){
k--;
if(k == 0){
return cur;
}
cur = cur.right;
}
else{
//otherwise we will traverse the left subtree and come back to current
//node by using threaded pointer from predecessor of current node
//first find the predecessor of cur
pre = cur.left;
while(pre.right != null && pre.right != cur){
pre = pre.right;
}

if(pre.right == null){
pre.right = cur;
cur = cur.left;
}
else{
//we traversed left subtree through threaded pointer and reached cur again
//so revert the threaded pointer and print out current node before traversing right subtree
pre.right = null;
k--;
if(k == 0){
return cur;
}
//now traverse right subtree
cur = cur.right;
}
}
}

return null;
}
}``````

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