kth-smallest-element-in-a-bst

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/28/kthtree1.jpg" style="width: 212px; height: 301px;" />
<pre>
Input: root = [3,1,4,null,2], k = 1
Output: 1
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/28/kthtree2.jpg" style="width: 382px; height: 302px;" />
<pre>
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in the tree is <code>n</code>.</li>
	<li><code>1 &lt;= k &lt;= n &lt;= 104</code></li>
	<li><code>0 &lt;= Node.val &lt;= 104</code></li>
</ul>

&nbsp;
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?

kthSmallest

Kth Smallest Element in a BST

Binary Tree Inorder Traversal

binary-tree-inorder-traversal

二叉树的中序遍历

Second Minimum Node In a Binary Tree

second-minimum-node-in-a-binary-tree

二叉树中第二小的节点

Tree

Depth-First Search

Binary Search Tree

Binary Tree

给定一个二叉搜索树的根节点 <code>root</code> ，和一个整数 <code>k</code> ，请你设计一个算法查找其中第&nbsp;<code>k</code>&nbsp;小的元素（从 1 开始计数）。

&nbsp;

示例 1：
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/28/kthtree1.jpg" style="width: 212px; height: 301px;" />
<pre>
输入：root = [3,1,4,null,2], k = 1
输出：1
</pre>

示例 2：
<img alt="" src="https://assets.leetcode.com/uploads/2021/01/28/kthtree2.jpg" style="width: 382px; height: 302px;" />
<pre>
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
</pre>

&nbsp;

&nbsp;

提示：

<ul>
	<li>树中的节点数为 <code>n</code> 。</li>
	<li><code>1 &lt;= k &lt;= n &lt;= 104</code></li>
	<li><code>0 &lt;= Node.val &lt;= 104</code></li>
</ul>

&nbsp;

进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 <code>k</code> 小的值，你将如何优化算法？