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

Problems
1

https://algo.monster/problems/kth_smallest_number_in_bst

2

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

3

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);
    }
}
4

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

5

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.

6

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]

7

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

8

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

9

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;
}