Building OABST using the Stack Algorithm

Initialize
Q[N]=T[N]
S=empty

Main Loop
while ( !((Q is empty) and $((size\_of(S))==1)) ) \mathbf{)}$
if $((size\_of(S)) \ge 2)$ and (the top 2 elements have the same levels)
then
$level_{top} = level\_of\_element (pop(S))$
Combine the two elements of the Queue Q which are referred
by the top two elements of the Stack
1. Create new internal node $new\_node$
2. $new\_node.level$ = StackTop.level - 1
3. $new\_node.weight$ = StackTop.weight
4. $new\_node.letter$ = (StackTop-1).letter
5. $new\_node.left\_child$ = (StackTop-1).node
6. $new\_node.right\_child$ = StackTop.node
Create new Stack element $new\_stack\_node$
1. $new\_stack\_node.level$ = $new\_node.level$
2. $new\_stack\_node.level$ = $new\_node.level$
3. $new\_stack\_node.reference$ = $address\_of(new\_node)$
4. pop(Stack)
5. pop(Stack)
6. $push(Stack, new\_stack\_node)$
else
Remove an element from the front of the queue Q and create a new
stack element $new\_stack\_node$ and push it on the top of the Stack:
1. $new\_stack\_node.level$ = QueueTop.level
2. $new\_stack\_node.letter$ = QueueTop.letter
3. $new\_stack\_node.reference$ = $address\_of(QueueTop)$
4. $push(Stack, new\_stack\_node)$
Advance the QTop pointer

End: OABST is built