Today I have done leetcode's April LeetCoding Challenge with cpp.

April LeetCoding Challenge 18

Description

Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:

Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

Constraints:

• The number of nodes in the tree is n.
• 1 <= k <= n <= 10^4
• 0 <= Node.val <= 10^4

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
  void traversal(TreeNode *root, int &rest, int &result) {
    if(!root) return;
    traversal(root->left, rest, result);
    if(result != -1) return;
    if((--rest) == 0) {
      result = root->val;
      return;
    }
    traversal(root->right, rest, result);
  }
public:
  int kthSmallest(TreeNode* root, int k) {
    int answer = -1;
    traversal(root, k, answer);
    return answer;
  }
};

// Accepted
// 93/93 cases passed (7 ms)
// Your runtime beats 99.88 % of cpp submissions
// Your memory usage beats 60.91 % of cpp submissions (24.2 MB)