// C# program to print nodes of extreme corners  

// of each level in alternate order  

using System; 

public class GFG 

{ 

    //INT class 

    public class INT 

    { 

        public int a; 

    } 

    // A binary tree node  

    public class Node  

    {  

        public int data;  

        public Node left, right;  

    };  

    // Utility function to allocate memory for a new node  

    static Node newNode(int data)  

    {  

        Node node = new Node();  

        node.data = data;  

        node.left = node.right = null;  

        return (node);  

    }  

    // Function that returns the height of the binary tree  

    static int height(Node root)  

    {  

        if (root == null)  

            return 0;  

​

        int lheight = height(root.left);  

        int rheight = height(root.right);  

​

        return Math.Max(lheight, rheight) + 1;  

    }  

    // Function performs level order traversal from right to  

    // left and prints the first node during the traversal  

    static void rightToLeft(Node root, int level, INT f)  

    {  

        if (root == null)  

            return;  

​

        // Checks for the value of f so that  

        // only first node is printed during  

        // the traversal and no other node is printed  

        if (level == 1 && f.a == 0)  

        {  

            Console.Write("{0} ", root.data);  

            f.a = 1;  

        }  

​

        else if (level > 1)  

        {  

            rightToLeft(root.right, level - 1, f);  

            rightToLeft(root.left, level - 1, f);  

        }  

    }  

    // Function performs level order traversal from left to  

    // right and prints the first node during the traversal  

    static void leftToRight(Node root, int level, INT f)  

    {  

        if (root == null)  

            return;  

​

        // Checks for the value of f so that  

        // only first node is printed during  

        // the traversal and no other node is printed  

        if (level == 1 && f.a == 1)  

        {  

            Console.Write("{0} ", root.data);  

            f.a = 0;  

        }  

​

        else if (level > 1) 

        {  

            leftToRight(root.left, level - 1, f);  

            leftToRight(root.right, level - 1, f);  

        }  

    }  

    // Function to print the extreme nodes of  

    // a given binary tree  

    static void printExtremeNodes(Node root)  

    {  

        // Stores height of binary tree  

        int h = height(root);  

​

        // Flag to mark the change in level  

        int flag = 0;  

​

        // To check if the extreme node of a  

        // particular level has been visited  

        INT f=new INT(); 

        f.a = 0;  

​

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

        {  

            // If flag is zero then traverse from  

            // right to left at the given level and  

            // print the first node during the traversal  

            if (flag == 0) 

            {  

                rightToLeft(root, i, f);  

                flag = 1;  

            }  

​

            // If flag is one then traverse from  

            // left to right at the given level and  

            // print the first node during the traversal  

            else if (flag == 1)  

            {  

                leftToRight(root, i, f);  

                flag = 0;  

            }  

        }  

​

        return;  

    }  

    // Driver code  

    public static void Main() 

    {  

        Node root = newNode(1);  

​

        root.left = newNode(2);  

        root.right = newNode(3);  

​

        root.left.left = newNode(4);  

        root.left.right = newNode(5);  

        root.right.right = newNode(7);  

​

        root.left.left.left = newNode(8);  

        root.left.left.right = newNode(9);  

        root.left.right.left = newNode(10);  

        root.left.right.right = newNode(11);  

        root.right.right.left = newNode(14);  

        root.right.right.right = newNode(15);  

​

        root.left.left.left.left = newNode(16);  

        root.left.left.left.right = newNode(17);  

        root.right.right.right.right = newNode(31);  

​

        printExtremeNodes(root);  

​

    }  

}