Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

**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

We provided one optimal solution.

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).

Note: Input and Output will already be taken care of.