How to find the kth smallest frequently?


  • 1
    A

    Follow up:
    What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

    I think this is about find next smallest element in BST, with time complexity being O(log(n))
    which should be better than O(k)

    Right?


  • 3
    V

    If we can modify the structure I think the answer is, we can add two int value to record how many elements are there in left child tree and right child tree. Like this:

    struct TreeNode{
    	int val;
    	TreeNode *left{nullptr}, *right{nullptr};
    	int leftCnt{0}, rightCnt{0};
    };
    

    When we try to insert or delete, update information from bottom to top.
    When we try to query, at most we will travel log n times.


  • 0
    Q

    Wouldn't this make node addition/removal very costly?


  • 0
    V

    Yeah, it may have some additional operations, but not so much. It's still O(log n) time complexity to add or remove.


  • 0
    C

    If we only focus on fixed k, we can make use of Morris Traversal with O(1) extra space.

    Record the kth nodeK at first with O(N) time and make use of empty right pointers. If a node smaller than nodeK is deleted, move nodeK to its next node; If a node larger than nodeK is deleted, move nodeK to its previous node. With Morris Traversal, we can modify nodeK with O(logn) time.

    The only bad thing is that a children node's right pointer may be point to its parent node, which means there's cycle in the BST. Then we need to take other operations carefully.


  • 0
    L
    This post is deleted!

  • 0
    Y

    Some (stupid) questions: 1. what do you mean by "move NodeK to its next/previous node"? If one node is removed/added, seems like many nodes need to be moved... 2. How about a node equal to nodeK(the nodeK itself) is removed? Thanks!


  • 0
    C

    thank you for attention!

    The structure is represented by pointer and BST is not balanced tree, so I think there's not much nodes to be moved. For example, if a node smaller or equal to nodeK will be removed, let's call it targetnode. We can first move nodeK to its next node, i.e. left most node in its right child or its right child, second remove the targetnode. To remove the targetnode, if it has both left child and right child, we can select the left most node it its right child as the root instead of the targetnode.

    Maybe a real example will be more helpful.


Log in to reply
 

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