Follow up solution with O(log(N)) time complexity - OrderStatisticsTree
Solution for the follow-up:\nFollow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest freque
Solution for the follow-up:\n**Follow up:** If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?\n\n**We can find kthSmallest in O(log(n)) if we build a tree in a certain way**. \nThe only addition we need - is to have "size" property for each TreeNode. Size can be found as:\n```\nnode.size = 1 + size(node.left) + size(node.right);\n```\n\nIf we know size for each node, we can implement FindByRank operation in O(log(n)) time:\nhttps://www.cs.yale.edu/homes/aspnes/pinewiki/OrderStatisticsTree.html\n\nSolution below will demonstrate how it works, however it is slower that regular O(n) solutions, because we are building the tree in custom way, calculating size for each node and only then calculating "Rank". \n**Solution below is O(n*log(n)): build tree (O(n*log(n)) + findRank (O(log(n))\nIf we had "size" property initially in the tree, we would have found kthSmallest (findByRank) in O(log(n)) time.**\n```\nclass Solution {\n//region precoditions\n    class TreeNodeWithSize {\n        int val;\n        int size;\n        TreeNodeWithSize left;\n        TreeNodeWithSize right;\n        TreeNodeWithSize(int val) { this.val = val; }\n    }\n\n    class OrderStatisticsTree {\n        TreeNodeWithSize root;\n\n       public int size(TreeNodeWithSize node){\n            if(node == null){\n                return 0;\n            }\n            return node.size;\n        }\n\n        public void put(TreeNodeWithSize node){\n            root = put(root, node);\n        }\n\n        private TreeNodeWithSize put(TreeNodeWithSize x, TreeNodeWithSize node){\n            if(x == null) {\n                node.size = 1;\n                return node;\n            }\n\n            if(node.val < x.val){\n                x.left = put(x.left, node);\n            }else if(node.val > x.val){\n                x.right = put(x.right, node);\n            }else{\n                x.val = node.val; //redundant, but leaving it here for display purposes\n            }\n            x.size = 1 + size(x.left) + size(x.right);\n            return x;\n        }\n\n        public int findByRank(int rank){\n            return findByRank(root, rank);\n        }\n\n        private int findByRank(TreeNodeWithSize root, int rank){\n            if(root == null) throw new IllegalArgumentException("empty tree");\n\n            int leftSize = 0;\n            if(root.left != null){\n                leftSize = root.left.size;\n            }\n\n            if(rank <= leftSize){\n                return findByRank(root.left, rank);\n            }else if(rank > leftSize + 1){\n                return findByRank(root.right, rank - leftSize - 1);\n            }\n            return root.val;\n        }\n    }\n//endregion\t\n\n//region problem solving\n    OrderStatisticsTree bst = new OrderStatisticsTree();\n    public int kthSmallest(TreeNode root, int k) {\n        buildOrderStatisticsTree(root);\n        return bst.findByRank(k);\n    }\n//endregion\t\n\n    public void buildOrderStatisticsTree(TreeNode node) {\n        if (node == null){\n            return;\n        }\n\n        bst.put(new TreeNodeWithSize(node.val));\n        buildOrderStatisticsTree(node.left);\n        buildOrderStatisticsTree(node.right);\n    }\n}\n```
['Binary Search Tree', 'Java']