[B] [C] [D]

Given the root node of a binary search tree, root, and an integer k, design an algorithm to find the KTH smallest element (counting from 1).

Example 1:

Input: root = [3,1,4,null,2], k = 1 output: 1Copy the code

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3 output: 3Copy the code

Tip:

  • The number of nodes in the tree is zeron 。
  • 1 <= k <= n <= 104
  • 0 <= Node.val <= 104

Advanced: If the binary search tree is constantly modified (insert/delete operations) and you need to find the KTH smallest value frequently, how do you optimize the algorithm?

Their thinking

Properties of binary search tree: For any subtree, the value of the root node is greater than that of the left child node, and the value of the root node is less than that of the right child node

Based on the above properties of binary search tree, if the binary search tree is traversed in order, a strictly ascending sequence will be obtained, and the KTH element in the sequence will be obtained, which is the KTH minimum element in the binary search tree.

Code implementation

Var kthSmallest = function(root, k) {var kthSmallest = function(root, k) {let num = 0,res; Function inorder(node){if(node === null) return; inorder(node.left); num++; If (num=== K){res = node.val; } inorder(node.right); } inorder(root); Return res; };Copy the code

At this point we have the KTH smallest element in the Leetcode-230-binary search tree

If you have any questions or suggestions, please leave a comment!