Kth Smallest Element in a BST

1package pkg5leetcode.official75;2 3/*4 * Kth Smallest Element in a BST | LC 2305 * APPROACH: Inorder traversal count nodes.6 * COMPLEXITY: Time O(n), Space O(h)7 */8public class official75_LC230KthSmallestElementInABST {9    /** Same shape as pkg5leetcode/common/TreeNode.java (nested for single-file runs). */10 11    static class TreeNode {12        int val;13        TreeNode left, right;14        TreeNode(int val) { this.val = val; }15    }16 17    static int kthSmallest(TreeNode root, int k) {18        java.util.Deque<TreeNode> st = new java.util.ArrayDeque<>();19        TreeNode cur = root;20        while (cur != null || !st.isEmpty()) {21            while (cur != null) { st.push(cur); cur = cur.left; }22            cur = st.pop();23            if (--k == 0) return cur.val;24            cur = cur.right;25        }26        return -1;27    }28 29    public static void main(String[] args) {30        TreeNode root = new TreeNode(3);31        root.left = new TreeNode(1); root.right = new TreeNode(4);32        root.left.right = new TreeNode(2);33        check(kthSmallest(root, 1) == 1, "case1");34        check(kthSmallest(root, 3) == 3, "case2");35        System.out.println("all tests passed");36    }37 38    static void check(boolean cond, String name) {39        if (!cond) throw new AssertionError("FAILED: " + name);40        System.out.println("  PASS " + name);41    }42}