Java divide-and-conquer solution considering augmenting tree structure for the follow-up
The idea behind the follow up question is what extra information is required for divide-and-conquer.  Basically is we can know the number of nodes on the left s
The idea behind the follow up question is what extra information is required for divide-and-conquer.  Basically is we can know the number of nodes on the left subtree, we get to know what is the position of the root node in the in-order traversal, which is basically the the kth number.  the left value can be saved in each node of the tree, and when we are finding the kth number, the complexity is O(lgn).\n\n       public class Solution {\n            public int kthSmallest(TreeNode root, int k) {\n                int left = nodeCount(root.left);  // this value can be saved in the root node\n                if(left + 1 == k) {\n                    return root.val;\n                } else if (left + 1 < k) {\n                    return kthSmallest(root.right, k - left - 1);\n                } else {\n                    return kthSmallest(root.left, k);\n                }\n            }\n            \n            private int nodeCount(TreeNode root) {\n                if(root == null) {\n                    return 0;\n                }\n                return 1 + nodeCount(root.left) + nodeCount(root.right);\n            }\n        }\n\t\t\nFollow up on the original post, I\'ve wrote a version that has populated the count in a customized Node.\n\n```\nclass Solution {\n    public int kthSmallest(TreeNode root, int k) {\n        Node node = buildTree(root);\n        return findKth(node, k);\n    }\n    \n    private int findKth(Node node, int k) {\n        if (node == null) {\n            return -1;\n        }\n        if (node.count < k - 1) {\n            return findKth(node.right, k - node.count - 1);\n        } else if (node.count > k - 1) {\n            return findKth(node.left, k);\n        }\n        return node.val;\n    }\n    \n    private Node buildTree(TreeNode root) {\n        if (root == null) {\n            return null;\n        }\n        Node node = new Node(root.val);\n        \n        int count = dfs(root.left);\n        node.count = count;\n        \n        node.left = buildTree(root.left);\n        node.right = buildTree(root.right);\n        return node;\n    }\n    \n    private int dfs(TreeNode root) {\n        if (root == null) {\n            return 0;\n        }\n        return dfs(root.left) + dfs(root.right) + 1;\n    }\n    \n    class Node {\n        Node left;\n        Node right;\n        int val;\n        int count;\n        Node (int val) {\n            this.val = val;\n        }\n    }\n}
['Divide and Conquer', 'Java']