using System;

using System.Collections.Generic;

​

public class Program

{

    /*     1

     *    / \

     *   2   5

     *  / \

     * 3   4

     *

     */

    static Node<string> root = new Node<string> ("Root")

    {

        Left = new Node<string>("Left of root") {

            Left = new Node<string>("TEST"),

            Right = new Node<string>("ABCDEF")

        },

        Right = new Node<string>("Right of root")

    };

    public static void Main()

    {

        /* Search a tree for a node whos data is equal to 'TEST' */

        bool contains_TEST = Contains<string>("TEST", root);

        if(contains_TEST)

        {

            Console.WriteLine("Root contains 'TEST'");

        }

        else

        {

            Console.WriteLine("Root does NOT contain 'TEST'");

        }

        /* Search a tree for a node whos data is equal to 'NOTHING' */

        bool contains_NOTHING = Contains<string>("NOTHING", root);

        if(contains_NOTHING)

        {

            Console.WriteLine("Root contains 'NOTHING'");

        }

        else

        {

            Console.WriteLine("Root does NOT contain 'NOTHING'");

        }

    }

    static bool Contains<T>(T item, Node<T> tree) {

        Stack<Node<T>> stack = new Stack<Node<T>>();

        stack.Push(tree); //Push the root node into the stack

        Node<T> current;

        do {

            current = stack.Pop(); //Get the last item that was added to the stack and remove it at the same time

            if (item.Equals(current.Data)) //If the item we just popped has its 'Data' property equal to the 'item'

            {

                Console.WriteLine("Found");

                return true; //then return true

            }

            //Otherwise add the left and right nodes to the stack if they exist.

            if(current.Left != null) stack.Push(current.Left);

            if(current.Right != null) stack.Push(current.Right);

        } while(stack.Count > 0);

        //If we've reached this point we've searched the entire tree and found nothing

        return false;

    }

}

​

class Node<T> {

    public T Data;

    public Node<T> Left;

    public Node<T> Right;

    public int balanceFactor;

    public Node(T Data)

    {

        this.Data = Data;

        Left = null;

        Right = null;

    }   

}