const countNodes = (root) => {
    if (!root) { return 0; }
    let cur = root;
    let stack = [];
    let count = 0;
    stack.push(cur);
    // Get total # of elements
    while (stack.length) {
        const cur = stack.pop();
        count++;
        if (cur.left) {
            stack.push(cur.left);
        }
        if (cur.right) {
            stack.push(cur.right);
        }
    }

    return count;
};



var kthSmallest = function(root, k) {
    // Constant space, recursive
    const countLeft = countNodes(root.left);
    if (countLeft >= k) {
        return kthSmallest(root.left, k);
    }
    if (k > countLeft + 1) {
        return kthSmallest(root.right, k - 1 - countLeft);
    }

    return root.val;


    // Linear space, O(nlogn + n)
//     const stack = [];
//     const final = [];
//     stack.push(root);
//     while (stack.length) {
//         const cur = stack.pop();
//         final.push(cur.val);
//         if (cur.right) {
//             stack.push(cur.right);
//         }
//         if (cur.left) {
//             stack.push(cur.left);
//         }
//     }

//     const sorted = final.sort((a, b) => {
//         return a - b;
//     });

//     console.log('sorted is', sorted);

//     return sorted[k - 1];

};