Kth Smallest Element in a BST

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        // return kthSmallestInorderIterative(root, k);
        return kthSmallestInorderRecursive(root, k);
        // return kthSmallestCountNodes(root, k);
    }

    public int kthSmallestInorderIterative(TreeNode root, int k) {
        if (root == null || k == 0) {
            return -1;
        }
        Stack<TreeNode> stack = new Stack<>();

        while (root != null) {
            stack.push(root);
            root = root.left;
        }

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            k--;
            if (k == 0) {
                return node.val;
            }
            node = node.right;
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
        }
        return -1;
    }

    public int kthSmallestInorderRecursive(TreeNode root, int k) {
        if (root == null || k == 0) {
            return -1;
        }

        int[] countAndResult = new int[2];
        countAndResult[0] = k;
        inOrderTraversalHelper(root, countAndResult);
        return countAndResult[1];
    }

    private void inOrderTraversalHelper(TreeNode node, int[] countAndResult) {
        if (node == null) {
            return;
        }
        inOrderTraversalHelper(node.left, countAndResult);
        if (countAndResult[0] == 0) {
            return;
        }
        countAndResult[0]--;
        if (countAndResult[0] == 0) {
            countAndResult[1] = node.val;
            return;
        }
        inOrderTraversalHelper(node.right, countAndResult);
    }

    public int kthSmallestCountNodes(TreeNode root, int k) {
        int leftSubtreeCount = countNodesInTree(root.left);
        if (k <= leftSubtreeCount) {
            return kthSmallestCountNodes(root.left, k);
        } else if (k > leftSubtreeCount + 1) {
            return kthSmallestCountNodes(root.right, k - leftSubtreeCount - 1);
        }
        return root.val;
    }

    private int countNodesInTree(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + countNodesInTree(node.left) + countNodesInTree(node.right);
    }
}