Kth Smallest Element in a BST

1package pkg5leetcode.blind75;2 3/*4 * Kth Smallest Element in a BST | LC 2305 * APPROACH: Inorder traversal returns kth visited node.6 * COMPLEXITY: Time O(h+k), Space O(h)7 */8public class blind75_LC230KthSmallestElementInBST {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 k, ans;18 19    static int kthSmallest(TreeNode root, int kVal) {20        k = kVal;21        inorder(root);22        return ans;23    }24 25    static void inorder(TreeNode node) {26        if (node == null || k == 0) return;27        inorder(node.left);28        if (--k == 0) ans = node.val;29        inorder(node.right);30    }31 32    public static void main(String[] args) {33        TreeNode root = new TreeNode(3);34        root.left = new TreeNode(1);35        root.right = new TreeNode(4);36        root.left.right = new TreeNode(2);37        check(kthSmallest(root, 1) == 1, "case1");38        check(kthSmallest(root, 3) == 3, "case2");39        System.out.println("all tests passed");40    }41 42    static void check(boolean cond, String name) {43        if (!cond) throw new AssertionError("FAILED: " + name);44        System.out.println("  PASS " + name);45    }46}