in-order traverse and binary search


  • 0
    N

    Hi,
    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);
            array.push_back(root->val);
            DFS(root->right, array);
        }
    }
    

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

    2.Optimization
    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.