in-order traverse and binary search

  • 0

    1 Inorder-traverse
    time complexity: O(n)
    space complexity: O(n) + O(logn)

    int kthSmallest(TreeNode* root, int k) {
        vector<int> array;
        DFS(root, array);
        return array[k - 1];
    void DFS(TreeNode* root, vector<int>& array) {
        if (root) {
            DFS(root->left, array);
            DFS(root->right, array);

    no-brain solution. Just use inorder property to get a sorted array and index the desired entry

    time complexity:
    average: O(nlogn)
    worst: O(n^2)

    int kthSmallest(TreeNode* root, int k) {
        int count = countNode(root->left);
        if (k == count + 1) return root->val;
        if (k < count + 1) return kthSmallest(root->left, k);
        else return kthSmallest(root->right, k - count - 1);
    int countNode(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        return countNode(root->left) + countNode(root->right) + 1;

    The first method requires us to traverse the entire tree, which is unnecessary. We can count how many nodes in a leftsubtree to decide the kth element may sit in left subtree or right subtree.
    Also I think this solution is for the follow-up. If we modify the tree very often and call kthsmallest frequently. We can add a "count" field to each node and update it in each dynamic operation. In this way kthsmallest can be done in o(lgN);

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.