:orphan:

Kth Smallest Element in a BST
=============================

.. highlight:: none

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

Given the ``root`` of a binary search tree, and an integer ``k``, return
*the* ``k``\ :sup:```th``` *smallest value (*\ **1-indexed**\ *) of all
the values of the nodes in the tree*.

 

**Example 1:**

|image1|

::


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

**Example 2:**

|image2|

::


   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``\ :sup:```4```
- ``0 <= Node.val <= 10``\ :sup:```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?

.. |image1| image:: https://assets.leetcode.com/uploads/2021/01/28/kthtree1.jpg
.. |image2| image:: https://assets.leetcode.com/uploads/2021/01/28/kthtree2.jpg

.. highlight:: python

Pattern
-------
Tree, Depth-First Search, Binary Search Tree, Binary Tree

Approaches
----------

.. tab-set::

    .. tab-item:: Inorder Traversal

        **Code**

        .. literalinclude:: ../problems/medium/kth-smallest-element-in-a-bst/kth_smallest_element_in_a_bst__inorder_traversal.py
            :language: python
            :lines: 9-

        **Test**

        >>> from kth_smallest_element_in_a_bst__inorder_traversal import kthSmallest, TreeNode
        >>> kthSmallest(TreeNode.from_list([3, 1, 4, None, 2]), 1)
        1
        >>> kthSmallest(TreeNode.from_list([5, 3, 6, 2, 4, None, None, 1]), 3)
        3

        .. autoclass:: kth_smallest_element_in_a_bst__inorder_traversal.TreeNode
           :members:
           :show-inheritance:
           :undoc-members:

        .. autofunction:: kth_smallest_element_in_a_bst__inorder_traversal.kthSmallest