Walk a BST In Order With a Stack

Complete BSTIterator so it hands out a tree's values one at a time, smallest first: next() returns the next value in sorted order, and hasNext() says whether any values are left.

Reminder: in-order traversal with your own stack. In a binary search tree every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger, so an in-order walk (left, node, right) meets the values smallest first. A recursive walk does the whole tree in one go. An iterator has to pause after every value, so instead of recursion it keeps its own stack of the nodes still waiting for their turn. A stack is last in, first out, which is exactly the order in which recursive calls finish.

The plan: push a node and every left child below it, all the way down. The top of the stack is then the smallest value not yet returned. When next() pops a node, the values that come right after it live in its right subtree, so push the left path of the popped node's right child before returning.

        8         new BSTIterator(root) pushes 8, 4, 2
       / \        next() pops 2 and returns 2
      4   12      next() pops 4, pushes 6, returns 4
     / \          next() pops 6 and returns 6
    2   6         next() pops 8, pushes 12, returns 8

Requirements: 1. Add a private helper pushLeftPath(Node node) that pushes node, moves to its left child, and repeats until it reaches null. 2. The constructor calls pushLeftPath(root), so right after construction stackSize() is the number of nodes on the path from the root down its left links (0 for an empty tree). 3. hasNext() returns true while the stack is not empty. 4. next() returns -1 when nothing is left. Otherwise it pops the top node, calls pushLeftPath on that node's right child, and returns the popped node's value. 5. Never copy the whole tree into the stack or into a list: the tests check stackSize() along the way. The tests build their trees with their own insert method.

The Node class is provided - do not rename it and do not add public to it, because a Java source file may contain only one public class.

Do NOT write a main method.