using System;
using System.Collections;
using System.IO;

// nodes of the binary tree
public class Node {
  public string val;
  public Node left, right;
  public Node(string v) { val = v; }
}

// binary tree; can be traversed with a foreach loop.
public class BinaryTree: IEnumerable {
  Node root = null;
  
  public void Insert(string val) {
    Node p = root, father = null;
    while (p != null) {
      father = p;
      if (val.CompareTo(p.val) < 0) p = p.left; else p = p.right;
    }
    Node q = new Node(val);
    if (root == null) root = q;
    else if (val.CompareTo(father.val) < 0) father.left = q;
    else father.right = q;
  }
  
  public Node Search(string val) {
    Node p = root;
    while (p != null && p.val != val) {
      if (val.CompareTo(p.val) < 0) p = p.left; else p = p.right;
    }
    return p;
  }
  
  public IEnumerator GetEnumerator() { return new TreeEnumerator(root); }
  
  
  // Enumerator for traversing the tree.
  // Remembers its way in a stack.
  class TreeEnumerator: IEnumerator {
    Stack stack; // nodes that have to be visited on the way back
    Node root;   // root of the tree
    Node cur;    // currently visited node of the tree
    
    public TreeEnumerator(Node p) { root = p; cur = null; }
    
    // Places cur on the node with the smallesr value in the tree with
    // root p and remembers the way to this node in a stack
    void SetCur(Node p) {  
      if (p.left == null)
        cur = p;
      else {
        stack.Push(p); SetCur(p.left);
      }
    }
    
    public object Current {
      get { return cur; }
    }
    
    public bool MoveNext() {
      if (cur == null) {
        Reset();
      } else {
        if (cur.right == null) cur = (Node)stack.Pop(); else SetCur(cur.right);
      }
      return cur != null;
    }
    
    public void Reset() {
      if (root == null) cur = null;
      else {
        stack = new Stack();
        stack.Push(null); SetCur(root);
      }
    }
  }
}

// Builds a binary tree and traverses it with a foreach loop
public class Trees {
  
  static void Main(string[] arg) {
    BinaryTree t = new BinaryTree();
    t.Insert("d"); t.Insert("b"); t.Insert("a"); t.Insert("c");
    t.Insert("f"); t.Insert("e");
    foreach (Node p in t) Console.WriteLine(p.val);
  }
}