using System;

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

namespace FixItSample
{

    public class BinarySearchTree
    { 
        private Node root; // root node
        private int size;  // number of nodes in the tree
   
        public bool remove(MyInput info) 
            { 
            Node parent = null;
            Node current = root;
            while (current != null) {
                int cmp = info.CompareTo(current.info);
                if (cmp < 0) {
                    parent = current;
                    current = current.left;
                } else if (cmp > 0) {
                    parent = current;
                    current = current.right;
                } else {
                    break;
                }
            }
            if (current == null) return false;
            Node change = removeNode(current);
            if (parent == null) {
                root = change;
            } else if (parent.left == current) {
                parent.left = change;
            } else {
                parent.right = change;
            }
            return true;
        }

    Node removeNode(Node current) 
    {
        size--;
        Node left = current.left, right = current.right;
        if (left == null) return right;
        if (right == null) return left;
        if (left.right == null) {
            current.info = left.info;
            current.left = left.left;
            return current;
        }
        Node temp = left;
        while (temp.right.right != null) {
            temp = temp.right;
        }
        current.info = temp.right.info;
        temp.right = temp.right.left;
        return current;
    }

    public bool repOk() 
    {
        // checks that empty tree has size zero
        if (root == null) return size == 0;
        // checks that the input is a tree
        if (!isAcyclic()) return false;
        // checks that size is consistent
        if (numNodes(root) != size) return false;
        // checks that data is ordered
        if (!isOrdered(root)) return false;
        return true;
    }  

    private bool isAcyclic() 
    {
        HashSet<NodeWrapper> visited = new HashSet<NodeWrapper>();
        visited.Add(new NodeWrapper(root));
        LinkedList<Node> workList = new LinkedList<Node>();
        workList.AddFirst(root);
        while (!(workList.Count == 0)) 
        {
            Node current = (Node)workList.Last.Value;
            workList.RemoveLast();
            if (current.left != null) {
                // checks that the tree has no cycle
                if (!visited.Add(new NodeWrapper(current.left))) 
                    return false;
                workList.AddFirst(current.left);
            }
            if (current.right != null) {
                // checks that the tree has no cycle
                if (!visited.Add(new NodeWrapper(current.right))) 
                    return false;
                workList.AddFirst(current.right);
            }
        }
        return true;
    }

    private int numNodes(Node n) 
    {
        if (n == null) return 0;
        return 1 + numNodes(n.left) + numNodes(n.right);
    }

    private bool isOrdered(Node n) 
    {
        return isOrdered(n, null, null);
    }

    private bool isOrdered(Node n, MyInput min, MyInput max)
    {
        if (n.info == null) return false;
        if ((min != null && n.info.CompareTo(min) <= 0) ||
            (max != null && n.info.CompareTo(max) >= 0))
            return false;
        if (n.left != null)
            if (!isOrdered(n.left, min, n.info))
                return false;
        if (n.right != null)
            if (!isOrdered(n.right, n.info, max))
                return false;
        return true;
    }
    
    public String toString() 
    {
        StringBuilder buf = new StringBuilder();
        buf.Append("{");
        if (root != null) 
            buf.Append(root.toString());
        buf.Append("}");
        return buf.ToString();
    }


    public void add(MyInput info) 
    {
        if (root == null) {
            root = new Node(info);
        } else {
            Node t = root;
            while (true) {
                if (t.info.CompareTo(info) < 0) {
                    if (t.right == null) {
                        t.right = new Node(info);
                        break;
                    } else {
                        t = t.right;
                    }
                } else if (t.info.CompareTo(info) > 0) {
                    if (t.left == null) {
                        t.left = new Node(info);
                        break;
                    } else {
                        t = t.left;
                    }
                } else { // no duplicates
                    return;
                }
            }
        }
        size++;
    }

    public bool containsNode(Node n) 
    {
        if (root == null) return false;
        LinkedList<Node> workList = new LinkedList<Node>();
        workList.AddFirst(root);
        while (workList.Count != 0) {
            Node current = (Node)workList.First.Value;
            workList.RemoveFirst();
            if (current == n) return true;
            if (current.left != null)
                workList.AddFirst(current.left);
            if (current.right != null)
                workList.AddFirst(current.right);
        }
        return false;
    }


    public bool contains(MyInput info) 
    {
        if (root == null) return false;
        LinkedList<Node> workList = new LinkedList<Node>();
        workList.AddFirst(root);
        while (workList.Count != 0) {
            Node current = (Node)workList.First.Value;
            workList.RemoveFirst();
            if (current.info.CompareTo(info) == 0) return true;
            if (current.left != null)
                workList.AddFirst(current.left);
            if (current.right != null)
                workList.AddFirst(current.right);
        }
        return false;
    }

	
    public bool equals(Object that)
    {
        if (!(that is BinarySearchTree))
            return false;
        BinarySearchTree b = (BinarySearchTree)that;
        if (size != b.size)
            return false;
        if (((root == null) && (b.root != null)) || 
            ((root != null) && (b.root == null)))
            return false;
        if ((root == null) && (b.root == null))
            return true;
        return root.equals(b.root);
    }
   }

    public class Node {
        public  Node left;  // left child
        public  Node right; // right child
        public  MyInput info; // data
        
        public Node(Node left, Node right, MyInput info)
        {
            this.left = left;
            this.right = right;
            this.info = info;
        }

        public Node(MyInput info)
        {
            this.info = info;
        }

        public string toString() 
        {
            HashSet<Node> visited = new HashSet<Node>();
            visited.Add(this);
            return toString(visited);
        }
        private string toString(HashSet<Node> visited) 
        {
            StringBuilder  buf = new StringBuilder();
            // buf.append(" ");
            // buf.append(System.identityHashCode(this));
            buf.Append(" {");
            if (left != null)
                if (visited.Add(left))
                    buf.Append(left.toString(visited));
                else
                    buf.Append("!tree");

            buf.Append("" + this.info + "");

            if (right != null)
                if (visited.Add(right))
                    buf.Append(right.toString(visited));
                else
                    buf.Append("!tree");
            buf.Append("} ");
            return buf.ToString();
        }

        public bool equals(Object that)
        {
            if (!(that is Node))
                return false;
            Node n = (Node)that;
			if (this.info == null) {
				if (n.info != null) {
					return false;
				}
			} else {
				if (this.info.CompareTo(n.info) != 0)
					return false;
			}
            bool b = true;
            if (left == null)
                b = b && (n.left == null);
            else
                b = b && (left.equals(n.left));
            if (right == null)
                b = b && (n.right == null);
            else 
                b = b && (right.equals(n.right));
            return b;
        }
                                            

    }

    public class MyInput 
    {
         private int o;

		 public MyInput(int i) {
			 o = i;
		 }

         public bool equals(Object that) {
             if (!(that is MyInput)) return false;
             return (o == ((MyInput)that).o);
         }

         public int hashCode() { return o.GetHashCode(); }

		 public int CompareTo(Object that) 
         {
             if (!(that is MyInput)) return -1;
             return o.CompareTo(((MyInput)that).o);
		 }		 
    }

      class NodeWrapper
      {
        Node node;
       
        public NodeWrapper(Node n)
        {
            this.node = n;
        }

        public bool equals(Object o)
        {
            if (!(o is NodeWrapper)) return false;
            return node == ((NodeWrapper)o).node;
        }
        public int hashCode(){
            return node.GetHashCode();
        }
    }

}