using System;

using System.Collections.Generic;

public class BinTreeTraversal

{   

    protected class Node

    {

        private Node left, right;

        private String data;

        public Node(String data)

        {

            this.data = data;

        }

        public Node getLeft(){ return this.left; }

        public Node getRight(){ return this.right; }

        public String getData(){ return this.data; }

        public void setLeft(Node left){ this.left = left; }

        public void setRight(Node right){ this.right = right; }

    }

    /*

     *  Current Node, Left Node, Right Node 

     */

    protected void preOrderTraverse(Node node)

    {

        if (node != null)

        {

            Console.Write(node.getData() + " ");

            preOrderTraverse(node.getLeft());

            preOrderTraverse(node.getRight());

        }

    }

    /*

     *  Left Node, Current Node, Right Node 

     */

    protected void inOrderTraverse(Node node)

    {

        if (node != null)

        {

            inOrderTraverse(node.getLeft());

            Console.Write(node.getData() + " ");

            inOrderTraverse(node.getRight());

        }

    }

    /*

     *  Left Node, Current Node, Right Node 

     */

    protected void postOrderTraverse(Node node)

    {

        if (node != null)

        {

            postOrderTraverse(node.getLeft());

            postOrderTraverse(node.getRight());

            Console.Write(node.getData() + " ");

        }

    }

    /*

     *  Breadth-First Search

     */

    protected void levelOrderTraverse(Node node)

    {

        Queue<Node> nQ = new Queue<Node>();

        if (node != null)

        {

            nQ.Enqueue(node);

        }

        while(nQ.Count != 0)

        {

            Node n = nQ.Dequeue();

            Console.Write(n.getData());

            if (n.getLeft() != null){ nQ.Enqueue(n.getLeft()); }

            if (n.getRight() != null){ nQ.Enqueue(n.getRight()); }

        }

    }

    protected int findHeight(Node node)

    {

        if (node == null){ return -1; }

        int heightLeft = findHeight(node.getLeft());    

        int heightRight = findHeight(node.getRight());  

        if (heightLeft > heightRight)

        {

            return heightLeft+1;

        }

        else

        {

            return heightRight+1;

        }

    }

    public static void Main()

    {

        BinTreeTraversal.Node root = new BinTreeTraversal.Node(")");

        BinTreeTraversal.Node a1 = new BinTreeTraversal.Node(")");

        BinTreeTraversal.Node a2 = new BinTreeTraversal.Node("5");

        BinTreeTraversal.Node b1 = new BinTreeTraversal.Node("x");

        BinTreeTraversal.Node b2 = new BinTreeTraversal.Node("2");

        BinTreeTraversal.Node b3 = new BinTreeTraversal.Node("(");

        BinTreeTraversal.Node b4 = new BinTreeTraversal.Node("x");

        BinTreeTraversal.Node c1 = new BinTreeTraversal.Node("(");

        BinTreeTraversal.Node c2 = new BinTreeTraversal.Node("89");

        BinTreeTraversal.Node c3 = new BinTreeTraversal.Node("2");

        BinTreeTraversal.Node c4 = new BinTreeTraversal.Node("x");

        BinTreeTraversal.Node c5 = new BinTreeTraversal.Node("-");

        BinTreeTraversal.Node c6 = new BinTreeTraversal.Node("11");

        BinTreeTraversal.Node d1 = new BinTreeTraversal.Node("2");

        BinTreeTraversal.Node d2 = new BinTreeTraversal.Node("^");

        BinTreeTraversal.Node d3 = new BinTreeTraversal.Node("+");

        BinTreeTraversal.Node d4 = new BinTreeTraversal.Node("181");

        BinTreeTraversal.Node d5 = new BinTreeTraversal.Node("98");

        root.setLeft(a1);

        root.setRight(a2);

        a1.setLeft(b1);

        a1.setRight(b2);

        a2.setLeft(b3);

        a2.setRight(b4);

        b1.setLeft(c1);

        b1.setRight(c2);

        b2.setLeft(c3);

        b2.setRight(c4);

        b4.setLeft(c5);

        b4.setRight(c6);

        c3.setLeft(d1);

        c3.setRight(d2);

        c4.setLeft(d3);

        c4.setRight(d4);

        c5.setLeft(d5);

        BinTreeTraversal binTT = new BinTreeTraversal(); 

        binTT.preOrderTraverse(root);

        Console.WriteLine("");

        binTT.inOrderTraverse(root);

        Console.WriteLine("");

        binTT.postOrderTraverse(root);

        Console.WriteLine("");

        binTT.levelOrderTraverse(root);

        Console.WriteLine("");

        Console.WriteLine(binTT.findHeight(root));

    }

}