O(k) Java solution


  • 12
    A

    The number of nodes (n) in the tree is irrelevant to the complexity. My code inorder traverse the tree and it stops when it finds the Kth node. The time complexity for this code is O(k).

    =======Update============

    The number of nodes in the tree does change the time complexity. The program actually goes to the left bottom node first and start from there to search for the Kth smallest. Thus the time complexity should be O(log(n) + K). What do you think ?

    public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        ArrayList<Integer> buffer = new ArrayList<Integer>();
        inorderSearch(root, buffer, k);
        return buffer.get(k-1);
    }
    public void inorderSearch(TreeNode node, ArrayList<Integer> buffer, int k){
        if(buffer.size() >= k)
            return;
        if(node.left != null){
            inorderSearch(node.left, buffer, k);
        }
        buffer.add(node.val);
        if(node.right != null){
            inorderSearch(node.right, buffer, k);
        }
    }
    

    }


  • 2
    J

    I have the same idea, but in iterative version.

    public class Solution {
        public int kthSmallest(TreeNode root, int k) {
            
            Stack<TreeNode> stack=new Stack<TreeNode>();
            int c=0;
            TreeNode cur=root;
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            while(!stack.isEmpty()){
                TreeNode ptr=stack.pop();
                c++;
                if(c==k)return ptr.val;
                TreeNode rt=ptr.right;
                while(rt!=null){
                    stack.push(rt);
                    rt=rt.left;
                }
            }
            return 0;
        }
    }

  • 1
    H

    The time complexity is O(log(n) + K) only if the tree is balanced. In the worst-case scenario the tree can have a height of n, thus the time complexity could be O(n)


  • 0
    G

    I believe the time complexity is simply O(n). K is a value between 1 and n, and the question did not describe K's distribution in this range. The best we can assume is that K is distributed evenly within the range, and hence the average value of K is just n/2. Therefore the average, rather than the worse case, time complexity of the solution is O(lg(n) + n/2) = O(n).


  • 1
    S

    I'm not sure why this is O(log(n)), I think this is O(n). You didn't skip any branch that is not null, which means you have a recursion towards the whole tree. A simple if condition to check if a child is null doesn't mean you skip a branch.


  • 0
    Z

    your code is different from almost all of others‘ which are recursive.
    I just think that so much people copy the code from others.
    so I voted you an up!


Log in to reply
 

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