Recursion makes tree traversals three lines long, but each can also be written with an explicit stack — which is what the recursion does behind the scenes. Write StackTraversals:
inorder(root): go left as far as possible, pushing the nodes; pop one, visit it, and continue with its right subtree;preorder(root): pop a node, visit it, push its right child then its left child;postorder(root): the order "node, right, left", reversed;- a class
InorderIterator implements Iterator<Integer>that delivers the keys in increasing order one at a time, keeping on its stack only the left branch still to be visited.
The first line of the input holds the keys to insert in a BST; the second, a number k. Print the three traversals and, with the iterator, the k smallest keys. For the input
50 30 70 20 40 60 80 35 45 65
4
the program prints
Inorder: [20, 30, 35, 40, 45, 50, 60, 65, 70, 80]
Preorder: [50, 30, 20, 40, 35, 45, 70, 60, 65, 80]
Postorder: [20, 35, 45, 40, 30, 65, 60, 80, 70, 50]
The 4 smallest keys: 20 30 35 40
The iterator has more keys: true