C# generic binary search tree with IEnumerable

A binary search tree needs to compare its elements. A generic constraint, where T : IComparable<T>, lets the tree call CompareTo on the elements and refuses to compile for a type that cannot be compared. Integers, strings, and DateTime already implement the interface, and your own classes can too.

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

class Tree<T> where T : IComparable<T> {
  private class Node {
    public T Value;
    public Node Left;
    public Node Right;
  }

  private Node root;

  public void Insert(T value) {
    root = Insert(root, value);
  }

  private Node Insert(Node node, T value) {
    if (node == null) {
      return new Node { Value = value };
    }
    int order = value.CompareTo(node.Value);
    if (order < 0) {
      node.Left = Insert(node.Left, value);
    } else if (order > 0) {
      node.Right = Insert(node.Right, value);
    }
    return node;
  }

  public IEnumerable<T> InOrder() {
    return InOrder(root);
  }

  private IEnumerable<T> InOrder(Node node) {
    if (node == null) {
      yield break;
    }
    foreach (T value in InOrder(node.Left)) {
      yield return value;
    }
    yield return node.Value;
    foreach (T value in InOrder(node.Right)) {
      yield return value;
    }
  }
}

class Program {
  static void Main() {
    var numbers = new Tree<int>();
    foreach (int n in new[] { 50, 30, 70, 20, 40, 60, 80, 40 }) {
      numbers.Insert(n);
    }
    Console.WriteLine(string.Join(" ", numbers.InOrder()));
    Console.WriteLine(string.Join(" ", numbers.InOrder().Take(3)));

    var words = new Tree<string>();
    foreach (string w in new[] { "pear", "fig", "apple", "kiwi" }) {
      words.Insert(w);
    }
    Console.WriteLine(string.Join(" ", words.InOrder()));
  }
}

Read the full lesson