Finding kthSmallestElement in the BST

Question

I am trying to solve the following question from LeetCode:

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

The aim is, given a BST, we have to find out the Kth-smallest element in it and return its value.

I could come up with a O(n) time and space solution myself. But another solution which I wrote with online help is far better:

    /**
 * 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 kthSmallestUtil(TreeNode* root, int& k) {
        if(!root) return -1;

        int value=kthSmallestUtil(root->left, k);
        if(!k) return value;

        k--;
        if(k==0) return root->val;

        return kthSmallestUtil(root->right, k);
    }

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

I have understood the above solution. I also debugged it (https://onlinegdb.com/BJnoIkrLM) by inserting break points at 29, 30, 33 and 37. However, I still feel a bit uneasy because of the following reason:

In case of the call kthSmallestUtil(root->left, k);, we pass the original value of k; we then (understandably) decrement the value of k for the current root (since we are doing in order traversal). But, when we again recurse for kthSmallestUtil(root->right, k);, why don't we pass the original value of k? Why does the right child get a 'preferential' treatment - a decremented value of k?

I know because of debugging how the values of k change and we get the final answer.. But I am seeking some intuition behind using the original value of k for the left child and the decremented value of k for the right child.

n0m4d3 n0m4d3 · Accepted Answer · 2018-02-04T20:26:46

This solutions seems to assume an ordered binary search tree. That means the left branch of the tree contains only smaller values than the current nodes val. Thus it first recurses into the left branch, decrementing k along the way, then if k is not 0 k is decremented for the current element. If k is still not 0 then the values in the right branch, all greater than the current nodes value, are considered.

What you need to understand is that the k being decremented in the k--; line is not the original value of k but the value of k after the traversal of the entire left branch.

The recursive calls all modify the same k because k is passed by reference and not by value

Finding kthSmallestElement in the BST

2 Answers