Kth Smallest Element in a BST recursive solution

Question

This code is to return kth smallest element in a BST.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
int fid;

void inorder(TreeNode* node, int& fid, int& k) {
if (!node) return;
inorder(node->left, fid, k);
if (!k) return;
fid = node->val;
k--;
inorder(node->right, fid, k);
}

int kthSmallest(TreeNode* root, int k) {
inorder(root, fid, k);
return fid;
}
};

It gave the correct answer. I thought I could simplify the code by combining inorder function and kthSmallest function together.

class Solution {
public:
int fid;
 int kthSmallest(TreeNode* root, int k) {
 if (!root) return fid;
kthSmallest(root->left, k);
if (!k) return fid;
fid = root->val;
k--;
kthSmallest(root->right, k);
return fid;
}
};

It gave the wrong answer. If I input BST{2,1} k=1, it will return 2 instead of 1. I couldn't figure out why two codes are different. Thanks for your help!

The Dark The Dark · Accepted Answer · 2016-04-28T00:14:53

There is a big difference between int& k (by reference) and int k (by value) as parameters.

In the first case, any changes that are made to k (such as k--) are reflected in the calling function's variable that was passed as a parameter.

In the second case, the function receives its own copy of k and any changes that are made to it won't affect the calling function.

You could change your kthSmallest to take k as a reference (int &), but that would change the way you would be allowed to call it. You probably still need a helper function, but you could put all of the code into it.

Kth Smallest Element in a BST recursive solution

1 Answers