using System;

using System.Collections.Generic;

/* Class containing left and right child of current

node and key value*/

class Node {

    public int key;

    public Node left, right;

    public Node(int item)

    {

        key = item;

        left = right = null;

    }

}

public class BinaryTree {

    // Root of Binary Tree

    Node root;

    BinaryTree() { root = null; }

    /* Given a binary tree, print its nodes in inorder

    1. Inorder Traversal (Practice):

    Follow the below steps to solve the problem:

    Traverse the left subtree, i.e., call Inorder(left-subtree)

    Visit the root

    Traverse the right subtree, i.e., call Inorder(right-subtree)

    Time Complexity: O(N)

    Auxiliary Space: O(log N)

    */

    void printInorder(Node node)

    {

        if (node == null)

            return;

        /* first recur on left child */

        printInorder(node.left);

        /* then print the data of node */

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

        /* now recur on right child */

        printInorder(node.right);

    }

        /* Given a binary tree, print its nodes in preorder

        Visit the root

        Traverse the left subtree, i.e., call Preorder(left-subtree)

        Traverse the right subtree, i.e., call Preorder(right-subtree)

        Time Complexity: O(N)

        Auxiliary Space: O(log N)

        */

    void printPreorder(Node node)

    {

        if (node == null)

            return;

        /* first print data of node */

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

        /* then recur on left subtree */

        printPreorder(node.left);

        /* now recur on right subtree */

        printPreorder(node.right);

    }

     /* 

     Given a binary tree, print its nodes according to the

    "bottom-up" postorder traversal. 

     Traverse the left subtree, i.e., call Postorder(left-subtree)

     Traverse the right subtree, i.e., call Postorder(right-subtree)

     Visit the root

     Time Complexity: O(N)

     Auxiliary Space: O(log N)*/

    void printPostorder(Node node)

    {

        if (node == null)

            return;

        // first recur on left subtree

        printPostorder(node.left);

        // then recur on right subtree

        printPostorder(node.right);

        // now deal with the node

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

    }

    // Wrappers over above recursive functions

    void printPostorder() { printPostorder(root); }

    // Wrappers over above recursive functions

    void printPreorder() { printPreorder(root); }

    // Wrappers over above recursive functions

    void printInorder() { printInorder(root); }

    /* function to print level order traversal of tree

       Time Complexity: O(N2), where N is the number of nodes in the skewed tree.

       So time complexity of printLevelOrder() is O(n) + O(n-1) + O(n-2) + .. + O(1) which is O(N2). 

        Auxiliary Space:  O(N) in the worst case. For a skewed tree, printGivenLevel() uses O(n) space for the call stack. 

        For a Balanced tree, the call stack uses O(log n) space, (i.e., the height of the balanced tree). */

    public virtual void printLevelOrder()

    {

        int h = height(root);

        int i;

        for (i = 1; i <= h; i++) {

            printCurrentLevel(root, i);

        }

    }

    /* Compute the "height" of a tree --

    the number of nodes along the longest

    path from the root node down to the

    farthest leaf node.*/

     int height(Node root)

    {

        if (root == null) {

            return 0;

        }

        else {

            /* compute height of each subtree */

            int lheight = height(root.left);

            int rheight = height(root.right);

            /* use the larger one */

            if (lheight > rheight) {

                return (lheight + 1);

            }

            else {

                return (rheight + 1);

            }

        }

    }

    /* Print nodes at the current level */

     void printCurrentLevel(Node root,

                                          int level)

    {

        if (root == null) {

            return;

        }

        if (level == 1) {

            Console.Write(root.key + " ");

        }

        else if (level > 1) {

            printCurrentLevel(root.left, level - 1);

            printCurrentLevel(root.right, level - 1);

        }

    }

      /* Given a binary tree. Print its nodes in level order using array for implementing queue 

        Time Complexity: O(N) where n is the number of nodes in the binary tree.

        Auxiliary Space: O(N) where n is the number of nodes in the binary tree.

        */

    void printLevelOrderWithQueue()

    {

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

        queue.Enqueue(root);

        while (queue.Count != 0) {

            Node tempNode = queue.Dequeue();

            Console.Write(tempNode.key + " ");

            /*Enqueue left child */

            if (tempNode.left != null) {

                queue.Enqueue(tempNode.left);

            }

            /*Enqueue right child */

            if (tempNode.right != null) {

                queue.Enqueue(tempNode.right);

            }

        }

    }

    /* Given a binary tree, print its

    nodes in reverse level order 

    Time Complexity: O(n), where n is the number of nodes in the binary tree. 

    Auxiliary Space: O(n), for stack and queue.*/

    void reverseLevelOrder(Node node)

    {

        Stack<Node> S = new Stack<Node>();

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

        Q.Enqueue(node);

        // Do something like normal level

        // order traversal order.Following

        // are the differences with normal

        // level order traversal

        // 1) Instead of printing a node, we push the node to stack

        // 2) Right subtree is visited before left subtree

        while (Q.Count>0)

        {

            /* Dequeue node and make it root */

            node = Q.Peek();

            Q.Dequeue();

            S.Push(node);

            /* Enqueue right child */

            if (node.right != null)

                // NOTE: RIGHT CHILD IS ENQUEUED BEFORE LEFT

                Q.Enqueue(node.right);

            /* Enqueue left child */

            if (node.left != null)

                Q.Enqueue(node.left);

        }

        // Now pop all items from stack

        // one by one and print them

        while (S.Count>0)

        {

            node = S.Peek();

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

            S.Pop();

        }

    }

    // Driver code

    public static void Main(String[] args)

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(5);

        Console.WriteLine(

            "\nInorder traversal of binary tree is ");

        tree.printInorder();

        Console.WriteLine();

           Console.WriteLine(

            "Preorder traversal of binary tree is ");

        tree.printPreorder();

        Console.WriteLine();

        Console.WriteLine(

            "\nPostorder traversal of binary tree is ");

        tree.printPostorder();

        Console.WriteLine();

        Console.WriteLine("Level order traversal "

                          + "of binary tree is ");

        tree.printLevelOrder();

        Console.WriteLine();

         Console.WriteLine("Level order traversal "

                          + "of binary tree with a Queue is");

        tree.printLevelOrderWithQueue();

        Console.WriteLine();

        Console.WriteLine("Level Order traversal of binary tree is :");

        tree.reverseLevelOrder(tree.root);

    }

}

​

/**

Notes

Given a Binary tree, Traverse it using DFS using recursion.

Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, 

trees can be traversed in different ways.Generally, there are 2 widely used ways for traversing trees:

​

DFS or Depth-First Search

BFS or Breadth-First Search

​

What is a Depth-first search?

DFS (Depth-first search) is a technique used for traversing trees or graphs. 

Here backtracking is used for traversal. In this traversal first, the deepest node is 

visited and then backtracks to its parent node if no sibling of that node exists

​

​

DFS Traversal of a Graph vs Tree:

In the graph, there might be cycles and disconnectivity. 

Unlike the graph, the tree does not contain a cycle and are always connected. 

So DFS of a tree is relatively easier. We can simply begin from a node, then traverse its adjacent (or children) without caring about cycles. 

And if we begin from a single node (root), and traverse this way, it is guaranteed that we traverse the whole tree as there is no dis-connectivity.

​

​

​

Given the root of the Binary Tree. The task is to print the Level order traversal of a tree is breadth first traversal for the tree. 

​

###Level Order Binary Tree Traversal using Recursion:

Print the level order traversal of the tree using recursive function to traverse all nodes of a level. 

Find height of tree and run depth first search and maintain current height, 

print nodes for every height from root and for 1 to height and match if the current height is equal to height of the iteration then print node’s data.

​

Follow the below steps to Implement the idea:

​

Run a for loop for counter i, i.e. current height from 1 to h (height of the tree).

Use DFS to traverse the tree and maintain height for the current node.

    If the Node is NULL then return;

    If level is 1 print(tree->data);

    Else if the level is greater than 1, then

        Recursively call to for tree->left, level-1.

        Recursively call to for tree->right, level-1.

###Level Order Binary Tree Traversal Using Queue

For each node, first, the node is visited and then it’s child nodes are put in a FIFO queue. Then again the first node is popped out and then it’s child nodes are put in a FIFO queue and repeat until queue becomes empty.

​

Follow the below steps to Implement the above idea:

​

Create an empty queue q and push root in q.

Run While loop until q is not empty. 

Initialize temp_node = q.front() and print temp_node->data.

    Push temp_node’s children i.e. temp_node -> left then temp_node -> right to q

    Pop front node from q.

###Reverse level order with a queue and stack

METHOD 2 (Using Queue and Stack) 

The idea is to use a deque(double-ended queue) to get the reverse level order. 

A deque allows insertion and deletion at both ends. If we do normal level order traversal and instead of printing a node, 

push the node to a stack and then print the contents of the deque, we get “5 4 3 2 1” for the above example tree, 

but the output should be “4 5 2 3 1”. So to get the correct sequence (left to right at every level), 

we process the children of a node in reverse order, we first push the right subtree to the deque, then process the left subtree.

**/