Difference between returning and not returning in recursion-CodePudding

I have written a program to print the Kth node from root of a binary tree.

// PRINT KTH NODE FROM ROOT (FUNCTION 1)
void printKth(node *root, int k){
    if (root == NULL){
        return;
    }
    if (k == 0){
        cout<<root -> data<<" ";
        return;
    }

    printKth(root -> left, k-1);
    printKth(root -> right, k-1);
}

For the below binary tree, The code prints

//          100     
//         /   \
//       80     120
//      /  \
//    40    60
// 
// OUTPUT - 80 120

The above function works fine until I add a return statement in the second and third last lines.

// PRINT KTH NODE FROM ROOT (FUNCTION 2)
void printKth(node *root, int k){
    if (root == NULL){
        return;
    }
    if (k == 0){
        cout<<root -> data<<" ";
        return;
    }

    return printKth(root -> left, k-1);    // ADDED RETURN STATEMENT
    return printKth(root -> right, k-1);   // ADDED RETURN STATEMENT
}

For the below binary tree, The code prints

//          100     
//         /   \
//       80     120
//      /  \
//    40    60
// 
// OUTPUT - 80

I can't understand what's happening when adding the return statement.

CodePudding user response：

There is nothing special about recursive functions. The second you return you are no longer evaluating the rest. You see that in your base cases since they don't evaluate the rest. When you add return the result of the call is returned and the last statement is never reached.

You function doesn't print the kth node but every node in the kth level in your first version. If you were to print the kth node you would have to return the current k and if it is still positive continue to recurse into the right tree.