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

namespace BST_Array
{
    class BST
    {
        private const int MAX_TREE_SIZE = 6;
        private const int NULL_INDEX = -999;

        private int[] keys, left, right, parent;
        private bool[] visited;
        private int treeSize;

        public BST()
        {
            keys = new int[MAX_TREE_SIZE];
            left = new int[MAX_TREE_SIZE];
            right = new int[MAX_TREE_SIZE];
            parent = new int[MAX_TREE_SIZE];

            visited = new bool[MAX_TREE_SIZE];
            treeSize = 0;
        }

        public void Add(int key)
        {

            this.keys[this.treeSize] = key;
            this.left[this.treeSize] = NULL_INDEX;
            this.right[this.treeSize] = NULL_INDEX;

            if (this.treeSize == 0)
            {
                this.parent[this.treeSize] = NULL_INDEX;
            }
            else
            {
                this.insert(treeSize, 0);
            }

            this.treeSize++;
        }

        public int Max()
        {
            if (this.treeSize == 0)
            { // if tree has no elements
                return 0;
            }
            else
            {
                return this.maxValue(0);
            }
        }

        private int maxValue(int index)
        {
            if (this.right[index] == NULL_INDEX)
            {
                return this.keys[index];
            }
            else
            {
                return this.maxValue(right[index]);
            }
        }

        public int Min()
        {
            if (this.treeSize == 0)
            { // if tree has no elements
                return 0;
            }
            else
            {
                return this.minValue(0);
            }
        }

        private int minValue(int index)
        {
            if (this.left[index] == NULL_INDEX)
            {
                return this.keys[index];
            }
            else
            {
                return this.minValue(left[index]);
            }
        }

        private void insert(int keyIndex, int parentIndex)
        {
            if (this.keys[keyIndex] <= this.keys[parentIndex])
            {// go left
                if (this.left[parentIndex] != NULL_INDEX)
                {
                    this.insert(keyIndex, this.left[parentIndex]);
                }
                else
                {
                    this.left[parentIndex] = keyIndex;
                    this.parent[keyIndex] = parentIndex;
                }
            }
            else
            {// go right
                if (this.right[parentIndex] != NULL_INDEX)
                {
                    this.insert(keyIndex, this.right[parentIndex]);
                }
                else
                {
                    this.right[parentIndex] = keyIndex;
                    this.parent[keyIndex] = parentIndex;
                }
            }


        }
    }
}