Description
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.
Examples:
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: 3Solution in Python
Python
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
# Helper function for in-order traversal
def inorder_traversal(node):
# If the node is None, return an empty list (base case)
if not node:
return []
# Recursively traverse the left subtree, then the current node, then the right subtree
return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right)
# Perform in-order traversal and return the k-1 th element (as k is 1-indexed)
return inorder_traversal(root)[k - 1]
Detailed Explanation:
- In-order Traversal:
- The helper function
inorder_traversalperforms an in-order traversal, which means it visits the left subtree, then the root node, and then the right subtree. - This traversal ensures that the nodes of the binary search tree are visited in ascending order.
- The helper function
- Base Case:
- If a node is
None, it returns an empty list. This is the base case for the recursion, ensuring that leaf nodes stop the recursion.
- If a node is
- Recursive Case:
- For each node, it recursively traverses the left subtree, adds the current node’s value to the result, and then recursively traverses the right subtree. The results are concatenated into a list.
- Return Statement:
- The full in-order traversal result is a sorted list of the tree’s values.
- Since
kis 1-indexed, the function returns the element at indexk - 1.
This approach ensures that we get the k-th smallest element efficiently using the properties of the binary search tree.
Solution in Javascript
JavaScript
var kthSmallest = function(root, k) {
// Helper function to perform in-order traversal
const inorderTraversal = (node) => {
// If the node is null, return an empty array (base case)
if (node === null) {
return [];
}
// Recursively traverse left subtree, then current node, then right subtree
return [...inorderTraversal(node.left), node.val, ...inorderTraversal(node.right)];
};
// Perform in-order traversal to get the elements in sorted order
const sortedValues = inorderTraversal(root);
// Return the k-th smallest element (1-indexed, so k-1 for 0-indexed array)
return sortedValues[k - 1];
};Solution in Java
Java
class Solution {
// Initialize a counter to track the number of nodes processed
private int count = 0;
// Variable to store the k-th smallest element
private int result = 0;
public int kthSmallest(TreeNode root, int k) {
// Perform in-order traversal
inorderTraversal(root, k);
// Return the k-th smallest value
return result;
}
// Helper function to perform in-order traversal
private void inorderTraversal(TreeNode node, int k) {
// Base case: if the node is null, return
if (node == null) {
return;
}
// Recursively traverse the left subtree
inorderTraversal(node.left, k);
// Increment the counter as we're visiting a node
count++;
// If the count matches k, we have found the k-th smallest element
if (count == k) {
result = node.val;
return;
}
// Recursively traverse the right subtree
inorderTraversal(node.right, k);
}
}Solution in C#
C#
public class Solution {
// Variable to keep track of the number of nodes processed
private int count = 0;
// Variable to store the k-th smallest value
private int result = 0;
public int KthSmallest(TreeNode root, int k) {
// Perform in-order traversal starting from the root
InorderTraversal(root, k);
// Return the k-th smallest value
return result;
}
// Helper function to perform in-order traversal
private void InorderTraversal(TreeNode node, int k) {
// If the node is null, return (base case)
if (node == null) {
return;
}
// Recursively traverse the left subtree
InorderTraversal(node.left, k);
// Increment the count of visited nodes
count++;
// If the count equals k, we've found the k-th smallest element
if (count == k) {
result = node.val;
return; // Exit early once the k-th element is found
}
// Recursively traverse the right subtree
InorderTraversal(node.right, k);
}
}