Tree

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

namespace BST
{
	public class BinarySearchTree<T> : IBinarySearchTree<T> where T : IComparable<T>
	{
		private T value;
		private IBinarySearchTree<T> left;
		private IBinarySearchTree<T> right;

		public BinarySearchTree(T value)
		{
			this.value = value;
			this.left = null;
			this.right = null;
		}

		public int Height { get => GetHeight(); }
		public IList<T> GetBFS()
		{
			IList<T> list = new List<T>();

			var queue = new Queue<IBinarySearchTree<T>>();

			queue.Enqueue(this);

			while (queue.Count > 0)
			{
				var node = queue.Dequeue();

				list.Add(node.GetRootValue());

				if (node.GetLeftTree() != null)
					queue.Enqueue(node.GetLeftTree());

				if (node.GetRightTree() != null)
					queue.Enqueue(node.GetRightTree());
			}

			return list;
		}

		public IList<T> GetInOrder()
		{
			IList<T> list = new List<T>();
			GetInOrder(this, list);
			return list;
		}

		public void GetInOrder(IBinarySearchTree<T> node, IList<T> list)
		{
			if (node.GetLeftTree() != null)
			{
				this.GetInOrder(node.GetLeftTree(), list);
			}

			list.Add(node.GetRootValue());

			if (node.GetRightTree() != null)
			{
				this.GetInOrder(node.GetRightTree(), list);
			}
		}
		public IBinarySearchTree<T> GetLeftTree()
		{
			return this.left;
		}

		public IList<T> GetPostOrder()
        {
			IList<T> list = new List<T>();
			GetPostOrder(this, list);
			return list;
		}

		public void GetPostOrder(IBinarySearchTree<T> node, IList<T> list)
		{
			if (node.GetLeftTree() != null)
			{
				this.GetPostOrder(node.GetLeftTree(), list);
			}

			if (node.GetRightTree() != null)
			{
				this.GetPostOrder(node.GetRightTree(), list);
			}

			list.Add(node.GetRootValue());
		}
		public IList<T> GetPreOrder()
		{
			IList<T> list = new List<T>();
			GetPreOrder(this, list);
			return list;
		}

		public void GetPreOrder(IBinarySearchTree<T> node, IList<T> list)
		{
			list.Add(node.GetRootValue());

			if (node.GetLeftTree() != null)
			{
				this.GetPreOrder(node.GetLeftTree(), list);
			}

			if (node.GetRightTree() != null)
			{
				this.GetPreOrder(node.GetRightTree(), list);
			}
		}


		public IBinarySearchTree<T> GetRightTree()
		{
			return this.right;
		}
		public T GetRootValue()
		{
			return this.value;
		}
		public void Insert(T element)
		{
			if(this.value != null)
            {
				if (this.value.CompareTo(element) > 0)
				{
					if (this.left != null)
					{
						this.left.Insert(element);
					}
					else
					{
						this.left = new BinarySearchTree<T>(element);
					}
				}
				else if(this.value.CompareTo(element) < 0)
				{
					if(this.right != null)
					{
						this.right.Insert(element);
					}
					else
					{
						this.right = new BinarySearchTree<T>(element);
					}
                }
                else
                {
					throw new ArgumentException("Eelement is already added!");
                }
            }
            else
            {
				this.value = element;
            }

		}


		public bool Search(T element)
		{
			return Search(element, this);
		}

		public bool Search(T element, IBinarySearchTree<T> node)
        {
			int result = element.CompareTo(node.GetRootValue());

			if (result == 0)
			{
				return true;
			}
            else if(result < 0)
            {
				if (node.GetLeftTree() != null)
					return Search(element, node.GetLeftTree());

				return false;
            }
            else
            {
				if (node.GetRightTree() != null)
					return Search(element, node.GetRightTree());

				return false;
			}
		}

		public int GetHeight()
        {
			return GetHeight(this);
		}

		public int GetHeight(IBinarySearchTree<T> node)
        {
			if (node == null)
            {
				return -1;
            }
            else
            {
				int heightL = GetHeight(node.GetLeftTree());
				int heightR = GetHeight(node.GetRightTree());

				if (heightL > heightR)
				{
					return heightL + 1;
				}
                else
                {
					return heightR + 1;
                }
			}

        }

		// Advanced task!
		public bool Remove(T value)
		{
			return this.Remove(value, this);
		}

		public bool Remove(T value, IBinarySearchTree<T> node)
        {
			if (node == null)
				return false;

			if(node.GetLeftTree() == null && node.GetRightTree() == null)
            {
				node = null;
			}

			return true;
		}
	}
}