Algorithm


Problem Name: 230. 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

Code Examples

#1 Code Example with C Programming

Code - C Programming


int count(struct TreeNode *node) {
    if (!node) return 0;
    return count(node->left) + count(node->right) + 1;
}
int kthSmallest(struct TreeNode* root, int k) {
    struct TreeNode *node = root;
    int n;
    n = count(node->left);
    if (n == k - 1) {
        return node->val;
    } else 
    if (n >= k) {
        return kthSmallest(node->left, k);
    }
    return kthSmallest(node->right, k - n - 1);
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
root = [3,1,4,null,2], k = 1

Output

x
+
cmd
1

#2 Code Example with Java Programming

Code - Java Programming


class Solution {
  public int kthSmallest(TreeNode root, int k) {
    Integer result = null;
    Stack < TreeNode> stack = new Stack<>();
    while (root != null) {
      stack.push(root);
      root = root.left;
    }
    while (k > 1 && !stack.isEmpty()) {
      TreeNode removed = stack.pop();
      TreeNode rightNode = removed.right;
      while (rightNode != null) {
        stack.push(rightNode);
        rightNode = rightNode.left;
      }
      k--;
    }
    return stack.peek().val;
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
root = [3,1,4,null,2], k = 1

Output

x
+
cmd
1

#3 Code Example with Javascript Programming

Code - Javascript Programming


const kthSmallest = function (root, k) {
  const st = []
  while (root !== null) {
    st.push(root)
    root = root.left
  }
  while (k !== 0) {
    const n = st.pop()
    k--
    if (k === 0) return n.val
    let right = n.right
    while (right !== null) {
      st.push(right)
      right = right.left
    }
  }
  return -1
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
root = [5,3,6,2,4,null,null,1], k = 3

Output

x
+
cmd
3

#4 Code Example with Python Programming

Code - Python Programming


class Solution:
    def __init__(self):
        self.k, self.res = 0, None
    def kthSmallest(self, root, k):
        if self.k < k and root.left: self.kthSmallest(root.left, k)
        self.k += 1
        if self.k == k: self.res = root.val
        if self.k < k and root.right: self.kthSmallest(root.right, k)
        return self.res
Copy The Code & Try With Live Editor

Input

x
+
cmd
root = [5,3,6,2,4,null,null,1], k = 3

Output

x
+
cmd
3

#5 Code Example with C# Programming

Code - C# Programming


using System.Collections.Generic;

namespace LeetCode
{
    public class _0230_KthSmallestElementInABST
    {
        public int KthSmallest(TreeNode root, int k)
        {
            var list = new List < int>();
            InOrder(root, k, list);
            return list[k - 1];
        }

        public void InOrder(TreeNode node, int k, IList < int> values)
        {
            if (values.Count >= k) return;
            if (node == null) return;

            InOrder(node.left, k, values);
            values.Add(node.val);
            InOrder(node.right, k, values);
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
root = [3,1,4,null,2], k = 1

Output

x
+
cmd
1
Advertisements

Demonstration


Previous
#229 Leetcode Majority Element II Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#231 Leetcode Power of Two Solution in C, C++, Java, JavaScript, Python, C# Leetcode