Inorden morris

inrMorris Inorder (Non-Recursive) Re-Visited
IFMSIG Winter Meeting 1999-2000 Hugh Gibbons Computer Science Dept., Trinity College Dublin

Knuth Challenge: Non-recursive inorder of a binary tree,without using an explicit stack or 'boolean flags'

Inorder Traversal (Recursive Version)

inorder(t : TREE[G]) : LIST[G] is do if is_empty (t) then Result := [ ] -- empty list else Result :=inorder(t.left) + [t.value] + + + inorder(t.right) end end -- Inorder

Notation + + is the join operator on lists

1

Approach to Non-Recursive version For non-empty t, we get, Inorder(t) =Inorder(t.left) + [t.value] + Inorder(t.right) + + = Inorder(t.left) + + Inorder(build(t.value, void, t.right)) = Inorder(b1) + Inorder(b2) + where b1 = t.left b2 = build(t.value, void, t.right)

Diagram:Inorder L R = Inorder L ++ Inorder R

2

Join operator on Trees Consider a function join s.t. join(b1, b2) ‘joins’ b2 to the right most of b1

Join

b1

b2

=

b1 b2

Note: Trees withthe operator, join, and the identity, empty, is a monoid. Inorder with join
Inorder L R R L = Inorder

i.e. inorder(t) = inorder(b1) + inorder(b2) + = inorder(join(b1,b2)) where b1 = t.left b2 =build(t.value, void, t.right)

3

join(b1,b2 : TREE[G]):TREE[G] is do if is_empty(b1) then result := b2 else result := build(b1.value, b1.left, Join(b1.right, b2)) end if end --join

MorrisInorder -- Abstract Code
Morris_Inorder(t0 : TREE[G]) : LIST[G] is t : TREE[G] s : LIST[G] do from t := t0 s := [ ] until t = void loop if t.left = void then t := t.right s := s + [t.value] + else t :=Join(t.left, build(t.value, void, t.right)) end end Result := s end -- Morris_Inorder

4

Binary Tree Structure/Class class TREE [Values] feature root : N is 1 size : N val : {1..size} f Valuesleft : N f N n Π2n -- total -- partial on N

right : N f N -- total n Π2n+1 first: N -- inorder first succ : N f N -- inorder succ left_sub : TREE right_sub : TREE etc. end -- TREE The Nodes in...