using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace ConsoleApplication1
{

    class Tree: IEnumerable
    {

        private int[] l;
        private int[] r;
        private int[] x;
        private int head = -1;
        private int root = -1;

        public Tree(int capacity = 10)
        {
            this.Capacity = capacity;
            Count = 0;
        }


        public int Capacity
        {
            get
            {
                return ((l == null)? 0 : l.Count());
            }
            private set
            {
                int size = Capacity;
                Array.Resize(ref l, value);
                Array.Resize(ref r, value);
                Array.Resize(ref x, value);
                for (int i = value - 1; i >= size; --i)
                {
                    l[i] = r[i] = -1;
                    x[i] = head;
                    head = i;
                }
            }
        }

        public int Count
        {
            get;
            private set;
        }

        private int getRoom()
        {
            if (head == -1) Capacity *= 2;
            int freeplace = head;
            head = x[head];
            return freeplace;
        }

        public bool addVertex(int value)
        {
            if (Count == 0) //root = -1;
            {
                root = getRoom();
                x[root] = value;
                return true;
            }

            int cur = root;
            while (true)
            {
                if (x[cur] == value)
                {
                    return false;
                }
                if (x[cur] > value)
                {
                    if (l[cur] != -1)
                    {
                        cur = l[cur];
                    }
                    else
                    {
                        l[cur] = getRoom();
                        x[l[cur]] = value;
                        return true;
                    }
                }
                else
                {
                    if (r[cur] != -1)
                    {
                        cur = r[cur];
                    }
                    else
                    {
                        r[cur] = getRoom();
                        x[r[cur]] = value;
                        return true;
                    }
                }
            }
        }

        public void deleteVertex(int value)
        {
            int cur = root;
            while (cur != -1)
            {

            }
        }

        public bool containsVertex(int val)
        {
            int cur = root;
            while (cur != -1 && x[cur] != val)
            {
                cur = ((val < x[cur]) ? l[cur] : r[cur]);
            }
            return cur != -1;
        }

        public IEnumerator GetEnumerator()
        {
            if (root == -1) yield break;
            Stack<int> s = new Stack<int>();
            s.Push(root);
            while (s.Count != 0)
            {
                int v = s.Peek();
                if (l[v] == -1)
                {
                    yield return x[v];
                    s.Pop();
                    if (r[v] != -1) s.Push(r[v]);
                }
                else //l[v] != -1
                {
                    s.Push(l[v]);
                }
            }
        }
    }
    class Program
    {
        static void Main(string[] args)
        {

        }
    }
}