In the previous post we spoke about how we can find the lowest common ancestor between two nodes. In the post we are going to tackle another LeetCode problem – finding the \(k^{th}\) smallest element in a binary search tree.

## The Problem

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

## Solution

To find the smallest \(k^{th}\) smallest element we need to do an in-order traversal of the tree while incrementing a counter. Once the counter is equal to \(k\) then we return the current node. Time complexity of the algorithm is \(O(h)\) and space complexity is also \(O(h)\). Here is the code:

```
public TreeNode<T> GetKthSmallestNode(int k)
{
var count = 0;
return FindKthSmallest(_root, k, ref count);
}
private TreeNode<T> FindKthSmallest(TreeNode<T> node, int k, ref int count)
{
if (node is null)
{
return null;
}
var left = FindKthSmallest(node.Left, k, ref count);
if (left != null)
{
return left;
}
count++;
if(count == k)
{
return node;
}
return FindKthSmallest(node.Right, k, ref count);
}
```

Please note that it is important to pass the `count`

by reference (trust me, I got burned once) since we are recursively calling `FindKthSmallest`

. Passing it by value throws everything under the bus since the function calls already on the call stack might be holding onto a wrong value.

This is how we find the \(k^{th}\) smallest element in a binary search tree. All the code is available on GitHub. Till next time, thanks so much for taking your time to read.

## Comments