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.


using System;
using System.Collections.Generic;
using System.Linq;
 
class Node
{
    int Value;
    Node Left;
    Node Right;
 
    Node(int value = default(int), Node left = default(Node), Node right = default(Node))
    {
        Value = value;
        Left = left;
        Right = right;
    }
 
    IEnumerable<int> Preorder()
    {
        yield return Value;
        if (Left != null)
            foreach (var value in Left.Preorder())
                yield return value;
        if (Right != null)
            foreach (var value in Right.Preorder())
                yield return value;
    }
 
    IEnumerable<int> Inorder()
    {
        if (Left != null)
            foreach (var value in Left.Inorder())
                yield return value;
        yield return Value;
        if (Right != null)
            foreach (var value in Right.Inorder())
                yield return value;
    }
 
    IEnumerable<int> Postorder()
    {
        if (Left != null)
            foreach (var value in Left.Postorder())
                yield return value;
        if (Right != null)
            foreach (var value in Right.Postorder())
                yield return value;
        yield return Value;
    }
 
    IEnumerable<int> LevelOrder()
    {
        var queue = new Queue<Node>();
        queue.Enqueue(this);
        while (queue.Any())
        {
            var node = queue.Dequeue();
            yield return node.Value;
            if (node.Left != null)
                queue.Enqueue(node.Left);
            if (node.Right != null)
                queue.Enqueue(node.Right);
        }
    }
 
    static void Main()
    {
        var tree = new Node(1, new Node(2, new Node(4, new Node(7)), new Node(5)), new Node(3, new Node(6, new Node(8), new Node(9))));
        foreach (var traversal in new Func<IEnumerable<int>>[] { tree.Preorder, tree.Inorder, tree.Postorder, tree.LevelOrder })
            Console.WriteLine("{0}:\t{1}", traversal.Method.Name, string.Join(" ", traversal()));
    }
}