Task

Implement a binary tree where each node carries an integer,   and implement:

   pre-order,
   in-order, 
   post-order,     and 
   level-order   traversal. 


Use those traversals to output the following tree:

         1
        / \
       /   \
      /     \
     2       3
    / \     /
   4   5   6
  /       / \
 7       8   9

The correct output should look like this:

preorder:    1 2 4 7 5 3 6 8 9
inorder:     7 4 2 5 1 8 6 9 3
postorder:   7 4 5 2 8 9 6 3 1
level-order: 1 2 3 4 5 6 7 8 9



See also

   Wikipedia article:   Tree traversal.


import extensions;
import extensions'routines;
import system'collections;
 
singleton DummyNode
{
    get generic()
        = EmptyEnumerable;
} 
 
class Node
{
    rprop int  Value;
    rprop Node Left;
    rprop Node Right;
 
    constructor new(int value)
    {
        Value := value
    }
 
    constructor new(int value, Node left)
    {
        Value := value;
        Left := left;
    }    
 
    constructor new(int value, Node left, Node right)
    {
        Value := value;
        Left := left;
        Right := right
    }
 
    Preorder = new Enumerable
    {
        Enumerator enumerator() = CompoundEnumerator.new(
                                        SingleEnumerable.new(Value), 
                                        (Left ?? DummyNode).Preorder, 
                                        (Right ?? DummyNode).Preorder);
    };
 
    Inorder = new Enumerable
    {
        Enumerator enumerator()
        {
            if (nil != Left)
            {
                ^ CompoundEnumerator.new(Left.Inorder, SingleEnumerable.new(Value), (Right ?? DummyNode).Inorder)
            }
            else
            {
                ^ SingleEnumerable.new(Value).enumerator()
            }
        }
    };
 
    Postorder = new Enumerable
    {
        Enumerator enumerator()
        {
            if (nil == Left)
            {
                ^ SingleEnumerable.new(Value).enumerator()
            }
            else if (nil == Right)
            {
                ^ CompoundEnumerator.new(Left.Postorder, SingleEnumerable.new(Value))
            }
            else
            {
                ^ CompoundEnumerator.new(Left.Postorder, Right.Postorder, SingleEnumerable.new(Value))
            }
        }
    };
 
    LevelOrder = new Enumerable
    {
        Queue<Node> queue := class Queue<Node>.allocate(4).push:self;
 
        Enumerator enumerator() = new Enumerator
        {
            bool next() = queue.isNotEmpty();
 
            get()
            {
                Node item := queue.pop();
                Node left := item.Left;
                Node right := item.Right;
 
                if (nil != left)
                {
                    queue.push(left)
                };
                if (nil != right)
                {
                    queue.push(right)
                };
 
                ^ item.Value
            }
 
            reset()
            {
                NotSupportedException.raise()
            }
 
            enumerable() = queue;
        };
    };
}
 
public program()
{
   var tree := Node.new(1, Node.new(2, Node.new(4, Node.new(7)), Node.new(5)), Node.new(3, Node.new(6, Node.new(8), Node.new(9))));
 
   console.printLine("Preorder  :", tree.Preorder);
   console.printLine("Inorder   :", tree.Inorder);
   console.printLine("Postorder :", tree.Postorder);
   console.printLine("LevelOrder:", tree.LevelOrder)
}