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


  • 0
    Z
    /**
     * 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;
        			}
        			
        			//threaded pointer not added - add it and go to left subtree to traverse
        			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;
        }
    }

Log in to reply
 

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