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.

Pseudocode

INORDER-TREE-WALK(x)

if x ≠ NULL

INORDER-TREE-WALK(left[x])

print key[x]

INORDER-TREE-WALK(right[x])