What if you could modify the BST node's structure?
If we could add a count field in the BST node class, it will take O(n) time when we calculate the count value for the whole tree, but after that, it will take O
If we could add a count field in the BST node class, it will take O(n) time when we calculate the count value for the whole tree, but after that, it will take O(logn) time when insert/delete a node or calculate the kth smallest element.\n\n       public class Solution {\n            public int kthSmallest(TreeNode root, int k) {\n                TreeNodeWithCount rootWithCount = buildTreeWithCount(root);\n                return kthSmallest(rootWithCount, k);\n            }\n            \n            private TreeNodeWithCount buildTreeWithCount(TreeNode root) {\n                if (root == null) return null;\n                TreeNodeWithCount rootWithCount = new TreeNodeWithCount(root.val);\n                rootWithCount.left = buildTreeWithCount(root.left);\n                rootWithCount.right = buildTreeWithCount(root.right);\n                if (rootWithCount.left != null) rootWithCount.count += rootWithCount.left.count;\n                if (rootWithCount.right != null) rootWithCount.count += rootWithCount.right.count;\n                return rootWithCount;\n            }\n            \n            private int kthSmallest(TreeNodeWithCount rootWithCount, int k) {\n                if (k <= 0 || k > rootWithCount.count) return -1;\n                if (rootWithCount.left != null) {\n                    if (rootWithCount.left.count >= k) return kthSmallest(rootWithCount.left, k);\n                    if (rootWithCount.left.count == k-1) return rootWithCount.val;\n                    return kthSmallest(rootWithCount.right, k-1-rootWithCount.left.count);\n                } else {\n                    if (k == 1) return rootWithCount.val;\n                    return kthSmallest(rootWithCount.right, k-1);\n                }\n            }\n            \n            class TreeNodeWithCount {\n                int val;\n                int count;\n                TreeNodeWithCount left;\n                TreeNodeWithCount right;\n                TreeNodeWithCount(int x) {val = x; count = 1;};\n            }\n        }
[]