Design an algorithm to perform an inorder traversal of a binary search tree using only a constant amount of extra space.
1 public void traverse(BST<Key,Value> bst) {
2 traverse(bst.root.left, bst.root);
3 }
4
5 private void traverse(Node current, Node parent) {
6 while (current != null) {
7 if (parent != null) {
8 parent.left = current.right;
9 current.right = parent;
10 }
11 if (current.left != null) {
12 parent = current;
13 current = current.left;
14 } else {
15 System.out.println(current.key);
16 current = current.right;
17 parent = null;
18 }
19 }
20 }