What the difference between my code "++count" and "count++" in the "Kth Smallest Element in a BST" solution?

0
votes

In the algorithm problem "Find the Kth Smallest Element in a BST" (https://leetcode.com/problems/kth-smallest-element-in-a-bst), my solution is below:

 public class Solution {
        private int count;
        public int kthSmallest(TreeNode root, int k) {
        if (root == null)
            return 0;
        int kth = kthSmallest(root.left, k);
        if (count == k)
            return kth;

        /********** section A *************/
        else if (++count == k)
            return root.val;
        /********** section A end *********/

        /********** section B *************/
        /*
        else if (count == k - 1) 
            return root.val;
        count++;
        */
        /********** section B end *********/

        /********** section C *************/
        /*
        else if (count == k - 1) {
            count++;
            return root.val;
        }
        */
        /********** section C end *********/
        return kthSmallest(root.right, k);
    }
}

In the leetcode online judge, section A is right and section B is wrong, which I think are equal to each other, I could not figure out the difference between the two sections.

P.S. Added the section C.

  • In section A

    count increase no matter ++count == k is true of false.

  • In section B

    count only increases when count == k - 1 is false, because when the count == k - 1 is true, the function will return and no longer execute any more. But Since we have got the right value returned, is it necessary to increase the value of count?

  • In section C

    count updated only when count == k - 1

  • Conclusion Section B is not equal to A, neither section C, when I integrated section B with section C, as showed below:

        else if (count == k - 1) {
        count++;
        return root.val;
    }
    count++;

it is equal to section A and passed the online judge, which is not elegant as section A.

:)

3
javaalgorithm
While using section B, your code wont compile, because you will have a dangling else statement below. Is that what you want to know? - Codebender
Section B would be same as section A if you would move count++; line before return statement. - Pshemo
@Codebender Yeah, there is a little bug, and I have fixed it, which will not affect my point. - mitcc
@Pshemo I have fixed the bug and the count in section B will increment no matter "count == k - 1" is true or false. But the solution on the online judge is still wrong with section B. - mitcc

3 Answers

3
votes

The value of the private instance variable count is updated in Section A regardless of whether the comparison succeeds or not.

That is, at the point of comparison occurring at the start of the section:

In Section A, if count == k - 1 holds true, the private count variable is incremented by 1 before root.val is returned.

In Section B, if count == k - 1 holds true, the count variable is not modified, and root.val is returned.

2
votes

In your code, in section A count gets incremented anyway, even if it does not equal k. In section B it gets incremented only if count DOES NOT equal k-1.

That's because when using ++i, the variable gets incremented first, then used (assigned, compared, etc).

1
votes
    int count=3;
   int k=5;
 if (++count == k)
      System.out.println("A"+ count);

  else if (count == k - 1) 
       System.out.println("B"+ count);

 System.out.println("C"+ count);

i write similar code

output; B4 C4

after first if case, count is anyway count =4

then k will be 4

finally second if case will work 

int count=3;
   int k=5;
 if (count++ == k)
      System.out.println("A"+ count);

  else if (count == k - 1) 
       System.out.println("B"+ count);

 System.out.println("C"+ count);

output: B4 C4

but if int count=4(for second code block )

output: C5