Time complexity is misleading/wrong in the description.

  • 0

    We can't actually achieve an O(1) (constant time) complexity with regards to number of nodes unless we have a very specific case, a balanced BST.

  • 1

    The question asks AVERAGE O(1) time so the type of BST doesn't matter.

  • -1
    but I think every time next() is called, we need to put the all left nodes in its right subtree, so average is not O(1) for time complexity, or did I miss something?

Log in to reply

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