Problem Statement

Implement an iterator over a binary tree with integer values. Your iterator will be initialized with the root node.

1. next() method must return the next number in the in-order traversal of the tree.

2. hasNext() method must return whether the next element exists.

Both methods must run in average O(1) time and use O(h) memory, where h is the height of the given tree.

Example

Input:

          200

          /    \

       100  300

Output: [100, 200, 300]

Notes

Input Parameters: There is only one argument named root denoting the root of the input tree.

Output: There is nothing to return as a whole. What the given method will do is described below:

Constructor/initializer: Initialize the iterator.

next(): Returns an integer denoting the next node value.

hasNext(): Returns a boolean denoting the next node's presence.

Constraints:

• 1

• -10^9

Solution

We provided one optimal solution.

optimal_solution.cpp:

Iterator must iterate from the leftmost to the rightmost node so that the nodes are traversed in-order. The leftmost node of a tree is the first element in the in-order traversal of a binary tree, so while initializing, we pushed root, root’s left child, root’s left child’s left child until we reach the leftmost node of the tree. After initialization, the leftmost node is at the top of the stack. When next() method is invoked, the top element from the stack is popped. As all left nodes are pushed from current top node, we push all left nodes starting from the top node’s right child. This process continues until all nodes are traversed and popped from the stack. For better understanding, please take a look at the solution.

Time Complexity:

O(n) where n is the number of nodes in the tree.

As we are iterating over all the nodes once, time complexity will be O(n).

Auxiliary Space:

O(h) where h is the height of the tree.

As we are using a stack to store nodes to be returned later and maximum nodes at a time will be h where h is the height of the tree, auxiliary space will be O(h). In the worst case, h will be equal to n such as left skewed or right skewed tree. So, the auxiliary space used in the worst case is O(h).

Space Complexity:

O(n) where n is the number of nodes in the tree.

As to store given tree it will take O(n) space and auxiliary

space is O(n) hence space complexity is O(n) + O(n) = O(n).

// -------- START --------
/*
    Complete the following methods
*/

class BTIterator{
private:
    stack iteratorStack;
    // insert all the left child into the stack rcursively
    void insertLeftNodes(TreeNode *root){
        while(root != NULL){
            iteratorStack.push(root);
            root = root->left_ptr;
        }
    }

public:
    // constructor
    BTIterator(TreeNode *root){
        // insert all the left nodes of current subtree
        insertLeftNodes(root);
    }
    
    // Check whether iterator has reached to the end
    bool hasNext(){
        return (!iteratorStack.empty());
    }

    // return the next smallest element of the tree
    int next(){
        // fetch the current smallest element
        TreeNode *currentRoot = iteratorStack.top();
        // remove it from the iterator
        iteratorStack.pop();
        // insert all the left left nodes of it's rigth subtree into the stack
        insertLeftNodes(currentRoot->right_ptr);
        // return current node value
        return currentRoot->val;
    }
};

// -------- END --------