Give a nonrecursive algorithm that performs an inorder tree walk. (Hint: an easy solution uses a stack as an auxiliary data structure. A more complicated, but elegant, solution uses no stack but assumes that we can test two pointers for equality.)

EASY-NONRECURSIVE-INORDER-TREE-WALK(TREE)

1 s = new stack<integer>

2 output = new list<integer>

3 s.push(TREE.root)

4 while(s.peek.hasLeftChild):

5     stack.push(stack.peek.getLeftChild)

6 while (stack.isNotEmpty):

7     node = stack.pop()

8     output.add(node.value)

9     if (node.hasRightChild):

10         stack.push(node.getRightChild)

11         while(stack.peek.hasLeftChild):

12             stack.push(stack.peek.getLeftChild)

13 return output

Oddly enough, none of the answer sources I rely on seem to have attempted the second algorithm hinted at. What I came up with meets the problem requirements but isn’t what I would describe as ‘elegant’. It makes use of a secondary procedure that validates whether a node has been included in the sorted output by way of structural comparison:

IS-NODE-NOT-IN-OUTPUT(node, output):

1 for (item in output):

2     if (item == node):

3         return false

4 return true

For convenience I construct the output as a list of tree nodes which must then be translated into a list of integers to truly satisfy the ask for an inorder tree walk.

MORE-COMPLICATED-BUT-ELEGANT-INORDER-TREE-WALK(TREE)

1 node = TREE.min

2 output = new list<treeNode>

3 while (node ≠ NIL):

4     if (node.hasLeftChild and IS-NODE-NOT-IN-OUTPUT(node.getLeftChild, output)):

5         node = node.getLeftChild

6     else if (IS-NODE-NOT-IN-OUTPUT(node, output)):

7         output.add(node)

8     else if (node.hasRightChild and IS-NODE-NOT-IN-OUTPUT(node.getRightChild, output)):

9         node = node.getRightChild

10     else if (node.hasParent and IS-NODE-NOT-IN-OUTPUT(node.getParent, output)):

11         node = node.getParent

12     else:

13         node = NIL

14 return output