Kth Smallest Integer in BST

Problem

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) in the tree.

A binary search tree satisfies the following constraints:

• The left subtree of every node contains only nodes with keys less than the node’s key.
• The right subtree of every node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees are also binary search trees.

Examples

Example 1:

Input: root = [2,1,3], k = 1

Output: 1

Example 2:

Input: root = [4,3,5,2,null], k = 4

Output: 5

Constraints

• 1 <= k <= The number of nodes in the tree <= 1000.
• 0 <= Node.val <= 1000

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the number of nodes in the given tree.

Solution

Perform DFS (inorder) and decrement counter. Once we reach count of 0, we found the kth smallest.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int kth_smallest;
        std::function<void(TreeNode*)> runner;
        runner = [&](TreeNode *node) {
            if (!node) { return; }
            // Count downt he lhs
            runner(node->left);
            // Count this node
            if (--k == 0) { 
                kth_smallest = node->val; 
                return;
            }
            // Count down the rhs
            runner(node->right);
        };
        runner(root);
        return kth_smallest;
    }
};