Implement an in-order tree iterator that support previous(), next()


  • 0
    U

    Supports previous(), next(), hasPrevious(), hasNext()
    Space complexity should be O(logn)


  • 0
    D

    In-order traverse the tree and store the sequence in an array. Then wrap the array by iterator?? Do I miss something? The tree may change(insert/delete node) when I have the Iterator?


  • 0
    C

    Generally, Iterators should be as lightweight as possible, and they should be fast to construct and pass around between functions. For instance, if you have a tree with 200k nodes and you want to store 100k iterators of those tree you would end up using 20 GB of memory.

    The proper solution keeps track of the current node and goes to the next / previous one when you call previous() / next().


  • 0
    D

    @cosminBoaca I see. So the TreeNode's struct would be as follows:
    struct TreeNode {
    TreeNode* left;
    TreeNode* right;
    int value;} So the tree node may not have the parent field right?


  • 0
    C

    In order for my solution to work, you need to have the parent pointer.


Log in to reply
 

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