# [LeetCode] Kth Smallest Element in a BST

This link suggests a concise C++ recursive solution. The original code may be hard to understand at first and I have rewritten the code below. You may need to run some examples with it to see how it works.

 1 class Solution {
2 public:
3     int kthSmallest(TreeNode* root, int k) {
4         return smallest(root, k);
5     }
6 private:
7     int smallest(TreeNode* node, int& k) {
8         if (!node) return -1;
9         int val = smallest(node -> left, k);
10         if (!k) return val;
11         if (!--k) return node -> val;
12         return smallest(node -> right, k);
13     }
14 };

The same author also posts three solutions which is more space-efficient in this link.  All of them reduce the O(n) space of the above code to O(k) space by using some nice data structures.

Personally I really love the soltuion using deque and I have rewritten it below.

 1 class Solution {
2 public:
3     int kthSmallest(TreeNode* root, int k) {
4         TreeNode* node = root;
5         deque<TreeNode*> nodes;
6         while (true) {
7             while (node) {
8                 nodes.push_front(node);
9                 if (nodes.size() > k)
10                     nodes.pop_back();
11                 node = node -> left;
12             }
13             node = nodes.front();
14             nodes.pop_front();
15             if (!--k) return node -> val;
16             node = node -> right;
17         }
18     }
19 };

|
8月前
Leetcode 230. Kth Smallest Element in a BST

51 1
|
Python
LeetCode 378. Kth S Element in a Sorted Matrix

85 0
|

LeetCode 229. Majority Element II

69 0
|

LeetCode 169. 多数元素 Majority Element
LeetCode 169. 多数元素 Majority Element
75 0
LeetCode 215. Kth Largest Element in an Array

66 0
|
1月前
|

【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-2
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
28 2
|
1月前
|

【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-1
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
34 2
|
1月前
|

【LeetCode刷题】二分查找：山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找：山脉数组的峰顶索引、寻找峰值
25 1
|
1月前
|

【LeetCode刷题】滑动窗口解决问题：串联所有单词的子串（困难）、最小覆盖子串（困难）
【LeetCode刷题】滑动窗口解决问题：串联所有单词的子串（困难）、最小覆盖子串（困难）
21 1
|
1月前
|

【LeetCode刷题】滑动窗口解决问题：水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题：水果成篮、找到字符串中所有字母异位词
27 1