using System;

public class Program

{

    public class binarytree

    {

        public class node

        { // Single element of tree (node)

            public string data;

            public node leftPointer;

            public node rightPointer;

        }

​

        public node root;

​

        public bool add(string item)

        {

            try //in case of memory overflow (full)

            {

                // store new item in memory and start looking from root of tree

                node newNode = new node();

                newNode.data = item;

                newNode.leftPointer = null;

                newNode.rightPointer = null;

                node currentNode = root;

                //Case that tree is empty

                if (currentNode == null)

                {

                    root = newNode;

                    return true;

                }

                else

                {

                    //work out where to put new item, by traversing tree until we find a left

                    node previous = currentNode;

                    while (currentNode != null)

                    {

                        previous = currentNode;

                        //compareTo compares two strings, returns val <0 if lower

                        if (item.CompareTo(currentNode.data)<0)

                        {

                            currentNode = currentNode.leftPointer;

                        }

                        else

                        {

                            currentNode = currentNode.rightPointer;

                        }

                    }

                    if (item.CompareTo(previous.data)<0)

                    {

                        previous.leftPointer = newNode;

                    }

                    else

                    {

                        previous.rightPointer = newNode;

                    }

                    return true;

                }

            }

            catch

            {

                return false;

            }

        }

    }

    public static void Main()

    {

        binarytree bt = new binarytree();

        bt.add("Here we have the root.");

        bt.add("And this is the left pointer.");

        bt.add("This is the right pointer.");

        bt.add("Extension task");

        bt.add("This is the 5th node.");

        bt.add("Final node");

        Console.WriteLine(bt.root.data);

        Console.WriteLine(bt.root.leftPointer.data);

        Console.WriteLine(bt.root.rightPointer.data);

        Console.WriteLine(bt.root.leftPointer.rightPointer.data);

        Console.WriteLine(bt.root.rightPointer.leftPointer.data);

        Console.WriteLine(bt.root.leftPointer.rightPointer.rightPointer.data);

    }

}