Given a binary search tree and an integer k, implement a method to find and return the k^{th} smallest node.

Example: 4 / \ 2 8 / \ 5 10 K = 2, Output = 4

Need a **hand?** Try out these hints, one at a time.

The trick here is to return the node that has the size of it's subtree is equal to

`k - 1`

. Keep in mind that this is a BST, not just a binary tree.
1. If `root`

is `null`

, return `null`

.

2. Else, if the left node of the `root`

is not null, find the size of the left subtree. If it's equal to `k - 1`

, return `root`

.

3. Else, if k is less than size, recurse through the left subtree. i.e. `return findKthSmallest(root.left, k)`

4. Recurse through the right subtree, with a new k -> k-leftSize-1 i.e.`return findKthSmallest(root.right, k-leftSize-1)`

public TreeNode findKthSmallest(TreeNode root, int k) { }

**C**

**Java**

**Python**