using System;

​

public class BinaryTree

{

    public class Node

    {

        public int item;

        public Node right;

        public Node left;

        public Node()

        {

            right = null;

            left = null;

        }

    }

    public Node root;

    public BinaryTree()

    {

        root = null;

    }

    public void InOrder(Node root)

    {

        if(root != null)

        {

        InOrder(root.left);

        Console.WriteLine(root.item+" ");

        InOrder(root.right);

        }

    }

    public void LeftMostNode(Node root)

    {

        while(root.left != null)

        {

            root = root.left;

        }

        Console.WriteLine("Left most:"+ root.item);

    }

    public void RightMostNode(Node root)

    {

        while(root.right != null)

        {

            root = root.right;

        }

        Console.WriteLine("Right most:"+ root.item);

    }

    public void RightNode(Node root)

    {

        Console.Write("Right nodes: ");

        while(root != null)

        {

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

            root = root.right;

        }   

    }

    public void LeftNode(Node root)

    {

        Console.Write("Left nodes: ");

        while(root != null)

        {

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

            root = root.left;

        }   

    }

    public void Insert(int item)

    {

        Node newNode = new Node();

        newNode.item = item;

         if(root == null)

         {

             root = newNode;

         }

        else

        {

            Node current = root;

            Node parent;

        while(true)

        {   

            parent = current;

            if(item<current.item)

            {

                current = current.left;

                if(current == null)

                {

                    parent.left = newNode;

                    break;

                }

            }

            else

            {

                current = current.right;

                if(current == null)

                {

                    parent.right = newNode;

                    break;

                }

            }

        }

    }

}

}

​

public class Program

{

    public static void Main()

    {

        BinaryTree bt = new BinaryTree();

        bt.Insert(10);

        bt.Insert(11);

        bt.Insert(9);

        bt.Insert(7);

        bt.Insert(12);

        bt.InOrder(bt.root);

        bt.LeftMostNode(bt.root);

        bt.RightMostNode(bt.root);

        bt.LeftNode(bt.root);

        bt.RightNode(bt.root);

    }

}