using System;
using System.Collections.Generic;

namespace ALGA {
	public class Node {
		public int number { get; private set; }

		public Node left = null;
		public Node right = null;

		public Node(int number) {
			this.number = number;
		}

		public void insert(int value) {
			if (number == value) return;

			if (value > number) {
				if (right != null)
					right.insert(value);
				else
					right = new Node(value);
			} else {
				if (left != null)
					left.insert(value);
				else
					left = new Node(value);
			}
		}

		public Node delete(int value) {
			return delete(this, value);
		}

		private Node delete(Node here, int value) {
			if (here == null) return null;

			if (value > here.number) here.right = delete(here.right, value);
			else if (value < here.number) here.left = delete(here.left, value);
			else {
				if (here.left == null) return here.right;
				if (here.right == null) return here.left;

				here.number = here.left.max().number;
				here.left = delete(here.left, here.number);
			}

			return here;
		}

		public Node min() {
			if (left == null) return this;
			return left.min();
		}

		public Node max() {
			if (right == null) return this;
			return right.max();
		}

		public int count() {
			int sum = 1;
			if (left != null) sum += left.count();
			if (right != null) sum += right.count();
			return sum;
		}

		public int depth() {
			return depth(this);
		}
		private int depth(Node here) {
			if (here == null) return 0;
			return 1 + Math.Max(depth(here.left), depth(here.right));
		}

		public Node find(int value) {
			if (number == value) return this;
			if (value > number && right != null) return right.find(value);
			if (value < number && left != null) return left.find(value);
			return null;
		}

		public List<int> flatten() {
			List<int> flat = new List<int>();

			if (left != null) flat.AddRange(left.flatten());
			flat.Add(number);
			if (right != null) flat.AddRange(right.flatten());

			return flat;
		}

		public List<int> flatten(int min, int max) {
			List<int> flat = new List<int>();

			if (min < number && left != null) flat.AddRange(left.flatten(min, max));
			if (min <= number && number <= max) flat.Add(number);
			if (right != null && number < max) flat.AddRange(right.flatten(min, max));

			return flat;
		}
	}
}