Understanding iterators in binary search trees
A binary search tree follows the special binary search property, which means the value of all the nodes in the left subtree of a node is smaller than it and the value of all the nodes in the right subtree is greater. Consequently, the inorder traversal that follows the left-node-right sequence traverses the tree in the sorted order(ascending) of values, while the reverse inorder traversal that follows the right-node-left sequence traverses the tree in the reverse sorted(descending) order.
The inorder traversal traverses the nodes in the sorted order, while the reverse-sorted order traverses them in the reverse-sorted order.
Consider that we have a binary search tree and must traverse all its nodes in the sorted(ascending) order of values. However, we don't want to traverse the entire tree at once, but move to the next node on demand, i.e. only when needed. The recursive or iterative inorder traversal traverses the entire tree all at once, and we cannot stop and resume the traversal from where we left off.
Liking the course? Check our discounted plans to continue learning.