Don't understand why this simple inOrder doesn't work (C)


  • 0
    S

    Hi there. I'm using a simple inorder and a counter to find the kith element.
    But I got the wrong case
    Input:
    [1,null,2], 2
    Output:
    1
    Expected:
    2

    Here's my code and I don't understand why this happened.

    int count = 0;
    int val;
    
    void inOrder(struct TreeNode* root, int k)
    {
        if (root) {
            inOrder(root->left, k);
            count++;
            if (count == k)
                val = root->val;
            inOrder(root->right, k);
        }
    }
    
    int kthSmallest(struct TreeNode* root, int k) {
        inOrder(root, k);
        return val;
    }

  • 0
    K

    Resetting the global variable "count" from within kthSmallest() will solve the problem you are encountering.

    int kthSmallest(struct TreeNode* root, int k) {
        count = 0;
        inOrder(root, k);
        return val;
    }
    

    See the following FAQ at https://leetcode.com/faq/

    Why does my code produce a different output compared to my local
    environment? First of all, LeetCode Judger executes all test cases
    using the same program instance, which means you need to check the
    following: Are there any global or static variables declared? Please
    avoid these variables if possible. If you must declare one, remember
    to reset them either in the default constructor or in the first line
    of your called method.

    Also, one small optimization that you could do is : return from the function once kth smallest is found, and traverse right subtree only if kthsmallest is not found already.

    void inOrder(struct TreeNode* root, int k)
    {
        if (root) {
            inOrder(root->left, k);
            count++;
            if (count == k) {
                val = root->val;
                return;
            }
            if(count<k) inOrder(root->right, k);
        }
    }

  • 0
    H

    because root==NULL returns false when root is wild pointer(not initialized) in C


  • 0

    Consider this test-case
    Assume the tree structure to be as shown below

                    10
                  /
                9
               /
             8
            /
          7
    

    if the value of k is 1 , we need to return the value as 7 and not 10.
    But your code would written 10.

    Correct me if I am wrong !


Log in to reply
 

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