# K-th Smallest Number In BST - Depth First Search / Binary Search Tree

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) {