Binary search tree: traverse

Genaral Information

Algorithmic problem: Sorted sequence: traverse

Type of algorithm: loop

Auxiliary data:

1. A stack S whose elements are pairs consisting of
   1. a natural number seenChildren in the range [math]\displaystyle{ \{0,1,2\} }[/math] and
   2. a binary search tree node node.
2. Pointers elem and elem' to stack elements.

Abstract View

Invariant: Before and after each iteration:

1. [math]\displaystyle{ S }[/math] contains all nodes on the path (called the current path) from the root to some binary search tree node (called the current node) in the order from the root to the current node (in particualr, the current node is the top element of [math]\displaystyle{ S }[/math]).
2. Let elem be some element of the stack:]
   1. If [math]\displaystyle{ elem.seendChildren = 0 }[/math], neither [math]\displaystyle{ elem.node.key }[/math] nor one of the keys in the subtree rooted at [math]\displaystyle{ elem.node.right }[/math] has been appended to [math]\displaystyle{ L }[/math] so far; possibly, some or all keys in the subtree rooted at [math]\displaystyle{ elem.node.left }[/math] have already been appended.
   2. If [math]\displaystyle{ elem.seenChildren = 1 }[/math], all keys in the subtree rooted at [math]\displaystyle{ elem.node.left }[/math] and, afterwards, [math]\displaystyle{ elem.node.key }[/math] have already been appended to [math]\displaystyle{ L }[/math]; possibly, some or all keys in the subtree rooted at [math]\displaystyle{ elem.node.right }[/math] have been appended as well.
   3. If [math]\displaystyle{ elem.seendChildren = 2 }[/math], all keys in the subtree rooted at [math]\displaystyle{ elem.node }[/math] have been appended to [math]\displaystyle{ L }[/math]

Variant: Indentify the current content of [math]\displaystyle{ S }[/math] with the string of length [math]\displaystyle{ |S| }[/math] over the alphabet [math]\displaystyle{ \{0,1,2\} }[/math] that is formed by the [math]\displaystyle{ seenChildren }[/math] values of the stack elements <in the order from the root to the current node). Then the current string immediately after the iteration

1. is either empty (which, clearly, is tantamount to [math]\displaystyle{ S }[/math] being empty),
2. or it is lexicographically larger than the string immediately before the iteration.

Break condition: [math]\displaystyle{ S }[/math] is empty.

Induction Basis

Abstract view: Initialize [math]\displaystyle{ S }[/math] with the root.

Implementation:

1. Create a new stack element [math]\displaystyle{ elem }[/math].
2. Set [math]\displaystyle{ elem.node := root }[/math].
3. Set [math]\displaystyle{ elem.seenChildren := 0 }[/math].
4. Ensure that [math]\displaystyle{ S }[/math] is empty.
5. [math]\displaystyle{ S.push(elem) }[/math].

Proof: All invariants are trivially fulfilled.

Pseudocode

INORDER-TREE-WALK(x)

if x ≠ NULL

INORDER-TREE-WALK(left[x])

print key[x]

INORDER-TREE-WALK(right[x])