using System;

//======================================================================
//  BinaryTree< K, V >
//======================================================================
class BinaryTree< K, V > where K: IComparable {
  
  class Node {
    public K key;
    public V val;
    public Node left, right;
    public Node(K key, V val) { this.key = key; this.val = val; }
  }
  
  Node root;
  Node foundNode;  // used in Contains to denote the found node
  
  // inserts a key-value pair into the tree
  public void Insert(K key, V val) {
    Node p = root, father = null;
    while (p != null) {
      father = p;
      int d = key.CompareTo(p.key);
      if (d == 0) return; // do not insert duplicates
      else if (d < 0) p = p.left; 
      else p = p.right;
    }
    // father points to the leaf under which the new node must be inserted
    Node n = new Node(key, val);
    if (root == null) root = n;
    else if (key.CompareTo(father.key) < 0) father.left = n;
    else father.right = n;
  }
  
  // returns true if the specified key is in the tree (sets foundNode)
  public bool Contains(K key) {
    Node p = root;
    while (p != null) {
      int d = key.CompareTo(p.key);
      if (d == 0) { foundNode = p; return true; }
      else if (d < 0) p = p.left;
      else p = p.right;
    }
    foundNode = null;
    return false;
  }
  
  // returns the value for the given key or throws an exception if not found
  public V this[K key] {
    get {
      if (Contains(key))
        return foundNode.val;
      else
        throw new Exception("-- no such value");
    }
  }
}

//---------------------------------------------------------------------
// Test program
//---------------------------------------------------------------------
class Test {
  
  static BinaryTree<string, int> phoneBook;

  static void Find(string name) {
    if (phoneBook.Contains(name))
      Console.WriteLine(name + ": " + phoneBook[name]);
    else
      Console.WriteLine(name + ": not found");
  }
  
  public static void Main() {
    phoneBook = new BinaryTree<string, int>();
    phoneBook.Insert("Jones", 1234);
    phoneBook.Insert("Adams", 2345);
    phoneBook.Insert("Miller", 3456);
    phoneBook.Insert("Watson", 4567);
    phoneBook.Insert("Smith", 5678);
    
    Find("Adams");
    Find("Adam");
    Find("Watson");
  }
}