Write the following traversals.

Depth-first Traversals: Pre-order, In-order, Post-order
Breadth-first Traversal: Level-order

void preOrderTraversalRecursive(Node n)
{
    if (n == null)
        return;

    visit(n);
    preOrderTraversalRecursive(n.left);
    preOrderTraversalRecursive(n.right);
}

void preOrderTraversalIterative(Node n)
{
    if (n == null)
        return;

    Stack<Node> s = new Stack<Node>();
    s.Push(n);

    while (s.Count > 0)
    {
        n = s.Pop();
        visit(n);

        if (n.right != null)
            s.Push(n.right);
        if (n.left != null)
            s.Push(n.left);
    }

}

void inOrderTraversalRecursive(Node n)
{
    if (n == null)
        return;

    inOrderTraversalRecursive(n.left);
    visit(n);
    inOrderTraversalRecursive(n.right);
}

void inOrderTraversalIterative(Node n)
{
    Stack<Node> s = new Stack<Node>();

    while(s.Count > 0 || n != null)
    {
        if (n != null)
        {
            s.Push(n);
            n = n.left;
        }
        else
        {
            n = s.Pop();
            visit(n);
            n = n.right;
        }
    }
}

void postOrderTraversalRecursive(Node n)
{
    if (n == null)
        return;
        
    postOrderTraversalRecursive(n.left);
    postOrderTraversalRecursive(n.right);
    visit(n);
}

void postOrderTraversalIterative(Node n)
{
    Stack<Node> s = new Stack<Node>();
    Node last = null, peek = null;

    while (s.Count > 0 || n != null)
    {
        if (n != null)
        {
            s.Push(n);
            n = n.left;
        }
        else
        {
            peek = s.Peek();
            if (peek.right != null && last != peek.right)
                n = peek.right;
            else
            {
                visit(peek);
                last = s.Pop();
            }
        }
    }
}

void levelOrderTraversal(Node n)
{
    if (n == null)
        return;
    
    Queue<Node> q = new Queue<Node>();
    q.Enqueue(n);

    while (q.Count > 0)
    {
        n = q.Dequeue();
        visit(n);

        if (n.left != null)
            q.Enqueue(n.left);
        if (n.right != null)
            q.Enqueue(n.right);
    }
}