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.

Induction Step

Abstract view:

1. If the left child of the current node has not yet been examined:
   1. If the left child of the current node exists, proceed to the left child.
2. Otherwise, if the right child of the current node has not yet been examined:
   1. Append the key of the current node to [math]\displaystyle{ L }[/math].
   2. If the right child of the current node exists, proceed to the right child.
3. Otherwise (that is, left and right child examined), proceed to the parent of the current node.

Implementation:

1. Set [math]\displaystyle{ elem := S.top() }[/math].
2. Set [math]\displaystyle{ node := elem.node }[/math]
3. If [math]\displaystyle{ elem.seenChildren = 0 }[/math]:
   1. If [math]\displaystyle{ node.left \neq void }[/math]:
      1. Create a new element [math]\displaystyle{ elem' }[/math].
      2. Set [math]\displaystyle{ elem'.node := node.left }[/math].
      3. Set [math]\displaystyle{ elem'.seenChildren := 0 }[/math].
      4. [math]\displaystyle{ S.push(elem') }[/math].
   2. Otherwise:
      1. Set [math]\displaystyle{ elem.seenChildren := 1 }[/math].
      2. [math]\displaystyle{ L.append(elem.node.key) }[/math].
4. Otherwise, if [math]\displaystyle{ elem.seenChildren = 1 }[/math]:
   1. If [math]\displaystyle{ node.right \neq void }[/math]:
      1. Create a new elem [math]\displaystyle{ elem' }[/math].
      2. Set [math]\displaystyle{ elem'.node := node.right }[/math].
      3. Set [math]\displaystyle{ elem'.seenChildren := 0 }[/math].
      4. [math]\displaystyle{ S.push(elem') }[/math].
   2. Otherwise, set [math]\displaystyle{ elem.seenChildren := 2 }[/math].
5. Otherwise, (that is [math]\displaystyle{ elem.seendChildren = 2 }[/math]).
   1. [math]\displaystyle{ S.pop() }[/math].
   2. If [math]\displaystyle{ S }[/math] is empty, terminate the algorithm.
   3. Set [math]\displaystyle{ elem := S.top() }[/math]
   4. Set [math]\displaystyle{ elem.seenChildren := elem.seendChildren + 1 }[/math].
   5. If [math]\displaystyle{ elem.seenChildren = 1 }[/math] and [math]\displaystyle{ elem.node.left \neq void }[/math] then: [math]\displaystyle{ L.append(elem.node.key) }[/math].

Correctness: Invariant #1 follows immediately from the fact that each push operation simply extends the current path and each pop operation cuts off the end node of the current path. Next consider Invariant #2.

Invariant #2 is trivially maintained both for [math]\displaystyle{ elem }[/math] and [math]\displaystyle{ elem' }[/math] in Steps 3.1 and 4.1 and [math]\displaystyle{ elem }[/math] in Step 3.2 and 4.2 (note the append operation in Step 2.2, which reflects the inclusion of the current node in Invariant 2.2). In Step 5, the algorithm returns from a non-empty subtree, so the increase of [math]\displaystyle{ seenChildren }[/math] and the append in case [math]\displaystyle{ seendChildren = 1 }[/math] are correct. Note that each key is appended only once because Step 3.2.2 applies only if the left child is empty, and Step 5.4, only if the left child is not empty. Finally, consider the variant. Whenever a new element is pushed, the new string is an extension of the old string, which is clearly lexicographically larger. On the other hand, whenever an element is removed from [math]\displaystyle{ S }[/math], Step 5.4 ensures that the new string is not just a prefix of the old string but is larger at the last position of the new string (which is the second last position of the old string).

Complexity

Statement: Linear in the length of the sequence in the worst case.

Proof: Each iteration of the loop takes constant time. Each node is visited in a most three iterations, viz. once with [math]\displaystyle{ seenChildren = 0,1,2 }[/math] respectively. This obvservation proves the claim.

Pseudocode

INORDER-TREE-WALK(x)

if x ≠ NULL

INORDER-TREE-WALK(left[x])

print key[x]

INORDER-TREE-WALK(right[x])