Understanding the reverse BST iterator

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

The algorithm for a reverse iterator is very similar to a forward iterator, as we only need to flip the order of traversal. The iterator class has the stack from the iterative traversal as a data member stack. Upon creating the iterator, we repeatedly move to the right 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 reverse inorder traversal.