Accepted by OJ, but does this solution meet the O(h) space requirement?


  • 0
    L

    This is a straight forward solution which recursively traverse the tree in-order and keep the values in a vector.
    Yet I'm not sure wether it has any draw back or does it even meet the O(h) requirement. It seems the vector keeps all the node value kind of exceed the O(h)?

        class BSTIterator {
    public:
      BSTIterator(TreeNode *root) {
        inOrder(root);
        m_idx = 0;
      }
    
      void inOrder(TreeNode* root){
        if(root == NULL)
          return;
        inOrder(root->left);
        m_values.push_back(root->val);
        inOrder(root->right);
      }
      /** @return whether we have a next smallest number */
      bool hasNext() {
        if(m_idx < m_values.size())
          return true;
        return false;
      }
    
      /** @return the next smallest number */
      int next() {
        return m_values[m_idx++];
      }
    private:
      vector<int> m_values;
      int m_idx;
    };

  • 1
    A

    I dont think your solution meets O(h) requirement even though its accepted by OJ. Keeping nodes in a vector using inorder traversal is essentially O(n) memory. Your program should be using O(h) memory.

    Hint: Try using stack and iterative version of pre-order traversal filling the stack as you go. I wrote the code that uses stack along with pre-order traversal and uses O(h) memory. I can share the code with you if you like.


  • 0
    L

    thanks for your answer


  • 0
    B

    Here's a good link for traversing a tree in-order by using a stack.

    http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/


Log in to reply
 

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