CareerCup

If there is a parent pointer, we can write a method which finds the successor of a given node.

So C# code might be something like this

class InorderIterator <T> {
    public InorderIterator (BinTree<T> tree) {
        if (tree == null) throw ...;
        _root = tree;
        _current = null;
        _firstMove = true;
    }
    public T Current {
        get { 
            if (_current == null) throw ...;
            return _current.Data;
        }
    }
    
    public bool MoveNext() {
        if (_firstMove) {
            _current = getSmallest(_root);
            _firstMove = false;
            return true;
        } else {
            _current = getSuccessor(_current);
            if (_current == null) {
                return false;
            }
            return true;
        }
    }
   
    public void Reset() {
        _firstMove = true;
        _current = null;
    }
    
    private BinTree<T> getSmallest(BinTree<T> node) {
        while (node.Left != null) {
            node = node.Left;
        }
        return node;
    }
    
    private BinTree<T> getSuccessor(BinTree <T> node) {
        if (node.Right != null) {
            return getSmallest(node.Right);
        }
        BinTree<T> parent = node.Parent;
        BinTree <T> current = node;
        while (parent && parent.Right == current) { 
            current = parent;
            parent = parent.Parent;
        }
        return parent;
    }
    
    private BinTree<T> _root;
    private BinTree<T> _current;
    private bool _firstMove; 
}

Solution does an initial inorder traversal of the tree and populating the queue with the nodes inorder.

class Node{
 public int data;
 public Node left;
 public Node right;
}
public class InorderTreeIterator implements Iterator {
 LinkedList<Node> nodeQueue;
 Node currentNode;

 public InorderTreeIterator(Node root){
  nodeQueue = new LinkedList<Node>
  initializeQueue(root);
 }
 public boolean hasNext(){
  return(!nodeQueue.empty());
 }
 public Node next(){
  if(hasNext())
   return(nodeQueue.removeFirst());
  return(null);
 }
 private initializeQueue(Node root){
  if(root = null)
   return;
  initializeQueue(root.left);
  nodeQueue.addLast(root);
  initializeQueue(root.right);
 }
}