JAVA Solution using Morris Traversal. Beats 95.15%


  • 1
    A

    Morris Traversal allows non-recursive in-order tree traversal without extra space usage.
    Geek for geeks has a good explanation about it: http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/

    //Morris Traversal
    
    /**
     * 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) {
            if(root == null || k <= 0) return 0;
            TreeNode node = root;
            while(node != null){
                if(node.left == null){
                    if(k == 1) return node.val;
                    --k;
                    node = node.right;
                }else{
                    TreeNode rightmost = node.left;
                    while(rightmost.right!= null){
                        rightmost = rightmost.right;
                    }
                    TreeNode temp = node.left;
                    node.left = null;
                    rightmost.right = node;
                    node = temp;
                }
            }
            
            return node.val;
        }
    }
    

Log in to reply
 

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