Kth Smallest Element in a BST LeetCode Solution | Easy Approach

Minimum Cost to Merge Stones
Share:

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 <= 104
  • 0 <= Node.val <= 104

Kth Smallest Element in a BST Solutions

Time: O(n)
Space: O(h)

C++

class Solution {
 public:
  int kthSmallest(TreeNode* root, int k) {
    const int leftCount = countNodes(root->left);

    if (leftCount == k - 1)
      return root->val;
    if (leftCount >= k)
      return kthSmallest(root->left, k);
    return kthSmallest(root->right, k - 1 - leftCount);  // leftCount < k
  }

 private:
  int countNodes(TreeNode* root) {
    if (!root)
      return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
  }
};

Java

 class Solution {
  public int kthSmallest(TreeNode root, int k) {
    final int leftCount = countNodes(root.left);

    if (leftCount == k - 1)
      return root.val;
    if (leftCount >= k)
      return kthSmallest(root.left, k);
    return kthSmallest(root.right, k - 1 - leftCount); // leftCount < k
  }

  private int countNodes(TreeNode root) {
    if (root == null)
      return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
  }
}

Python

  class Solution:
  def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
    def countNodes(root: Optional[TreeNode]) -> int:
      if not root:
        return 0
      return 1 + countNodes(root.left) + countNodes(root.right)

    leftCount = countNodes(root.left)

    if leftCount == k - 1:
      return root.val
    if leftCount >= k:
      return self.kthSmallest(root.left, k)
    return self.kthSmallest(root.right, k - 1 - leftCount)  # leftCount < k

Watch Tutorial

Checkout more Solutions here

Leave a Comment

Your email address will not be published. Required fields are marked *

x