6-line java solution that beats 95.98%


  • 1
    B

    Nothing fancy, standard inorder-traversal that stops/returns immediately when finding the kth node.
    ct --> a global instance variable increases onlyu when ct < k and cur_node != null

    public class Solution {
        int ct = 0; 
        public int kthSmallest(TreeNode root, int k) {
            if(root == null) return 0;            
            int res = kthSmallest(root.left, k);  
            if(ct == k) return res;               
            else if(++ct == k) return root.val;  
            return kthSmallest(root.right, k);  
        }
    }
    

  • 0
    I

    I tried your code, and it did beat 96% as of today.
    Below is what I wrote, I think it's actually the same as yours.
    However, my code beats only 49%.
    I cannot tell why.

    int count = 0;
    int val = -1;

    public int kthSmallest(TreeNode root, int k) {
        search(root, k);
        return val;
    }
    
    private void search(final TreeNode node, final int k) {
        if(node == null) return;
        
        search(node.left, k);
        
        if(count == k) return;
        
        count++;
        
        if(count == k) {
            val = node.val;
            return;
        }
        
        search(node.right, k);
    }

Log in to reply
 

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