Need to specify that -1 or negative values are not allowed in the node values for this solution to work

my solution with in order traversal:

```
static int count;
static int result = 0;
public static int kthSmallest(Node<Integer> bst, int k) {
count = k;
helper(bst);
return result;
}
private static void helper(Node<Integer> root) {
if (root == null) return;
helper(root.left);
count--;
if (count == 0) result = root.val;
else {
helper(root.right);
}
}
```

Simpler solution to achieve o(k) time and o(n) space:

def kth_smallest(bst: Node, k: int) → int:

# WRITE YOUR BRILLIANT CODE HERE

counter = 0

res = float(‘inf’)

def DFS(root):

if not root:

return

nonlocal counter

nonlocal res

DFS(root.left)

counter+=1

if counter == k:

res = root.val

DFS(root.right)

DFS(bst)

return res

By property, inorder traversal of a binary tree returns a sorted array.

Now, kth smallest element can just be selected by the index k or k-1 based on whether we have 1-indexing or 0-indexing respectively.

Simpler solution:

def kth_smallest(bst: Node, k: int) → int:

arr = []

def dfs(bst):

if bst is not None:

dfs(bst.left)

arr.append(bst.val)

dfs(bst.right)

dfs(bst)

return arr[k-1]

Good one, but many times in interview they hate global variables.

In Python you can get around this by using nested functions. That’s what they’re there for - situations like this where the code is so much cleaner using a ‘global’, but globals are ugly. So instead you make a local, and then have a recursive inner function that utilizes the outer function’s local

You may go an inorder traversal as mentioned also by another commentator and you would have a sorted list at the end and then access the kth elements directly from there.

public static int kthSmallest(final Node bst, final int k) {

if (bst == null) {

return -1;

}

final List nodes = new ArrayList<>();

inoderTraverse(bst, nodes);

return nodes.get(k - 1);

}

```
private static void inoderTraverse(final Node<Integer> root, final List<Integer> nodes) {
if (root == null) {
return;
}
if (root.left == null) {
nodes.add(root.val);
} else {
inoderTraverse(root.left, nodes);
nodes.add(root.val);
}
inoderTraverse(root.right, nodes);
return;
}
```