Understanding the forward BST iterator

For a binary search tree, the forward iterator traverses the nodes of a tree on demand in the inorder sequence. This allows traversing the tree in the sorted order(ascending) of values, one node at a time, moving to the next node only when explicitly requested.

We can modify the iterative inorder traversal algorithm by separating the traversal to the left and right subtrees to devise an algorithm for the forward iterator. The iterator class has the stack from the iterative traversal as a data member stack. Upon creating the iterator, we repeatedly move to the left of each node starting from the root node and add all the nodes to the stack until we hit a null reference. At this point, the node at the top of the stack is the first node from the inorder traversal.