import java.util.ArrayList;

import java.util.List;

/**

* Definition for binary tree

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

public class BSTIterator

{

List<TreeNode> visit = new ArrayList<>();

int _count = 0;

int _step = 0;

public BSTIterator( TreeNode root )

{

inOrder( root );

_count = visit.size();

}

public void inOrder( TreeNode root )

{

if ( root == null )

return;

inOrder( root.left );

visit.add( root );

inOrder( root.right );

}

/** @return whether we have a next smallest number */

public boolean hasNext()

{

return _count - _step == 0 ? false : true;

}

/** @return the next smallest number */

public int next()

{

int next = visit.get( _step ).val;

_step++;

return next;

}

}

/**

* Your BSTIterator will be called like this:

* BSTIterator i = new BSTIterator(root);

* while (i.hasNext()) v[f()] = i.next();

*/