C# generic binary search tree with IEnumerable

Constrain the element type with IComparable<T> and expose the sorted values with yield return.

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()));
  }
}

Output

20 30 40 50 60 70 80
20 30 40
apple fig kiwi pear

Explanation

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.

yield return turns a method into an iterator: it produces values one at a time, and the caller can use foreach or LINQ on them. A recursive in-order traversal yields the left subtree, then the node, then the right subtree, so the values come out sorted. The traversal is lazy, so taking only the first few values does not visit the whole tree.

Explore the dry run

Guided walkthroughReady

1using System;

2using System.Collections.Generic;

3using System.Linq;

5class Tree<T> where T : IComparable<T> {

6 private class Node {

7 public T Value;

8 public Node Left;

9 public Node Right;

10 }

12 private Node root;

14 public void Insert(T value) {

15 root = Insert(root, value);

16 }

18 private Node Insert(Node node, T value) {

19 if (node == null) {

20 return new Node { Value = value };

21 }

22 int order = value.CompareTo(node.Value);

23 if (order < 0) {

24 node.Left = Insert(node.Left, value);

25 } else if (order > 0) {

26 node.Right = Insert(node.Right, value);

27 }

28 return node;

29 }

31 public IEnumerable<T> InOrder() {

32 return InOrder(root);

33 }

35 private IEnumerable<T> InOrder(Node node) {

36 if (node == null) {

37 yield break;

38 }

39 foreach (T value in InOrder(node.Left)) {

40 yield return value;

41 }

42 yield return node.Value;

43 foreach (T value in InOrder(node.Right)) {

44 yield return value;

45 }

46 }

47}

49class Program {

50 static void Main() {

51 var numbers = new Tree<int>();

52 foreach (int n in new[] { 50, 30, 70, 20, 40, 60, 80, 40 }) {

53 numbers.Insert(n);

54 }

55 Console.WriteLine(string.Join(" ", numbers.InOrder()));

56 Console.WriteLine(string.Join(" ", numbers.InOrder().Take(3)));

58 var words = new Tree<string>();

59 foreach (string w in new[] { "pear", "fig", "apple", "kiwi" }) {

60 words.Insert(w);

61 }

62 Console.WriteLine(string.Join(" ", words.InOrder()));

63 }

64}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
The constraint guarantees that CompareTo is available on every element.	`—`	—
Negative means go left, positive means go right, zero means a duplicate that is ignored.	`—`	—
Yield every value of the left subtree first.	`—`	—
Then the node itself, so the sequence is sorted.	`—`	—
The sorted values; the duplicate 40 was ignored.	`—`	20 30 40 50 60 70 80
Take(3) stops the iteration early, so only the left part of the tree is visited.	`—`	20 30 40 50 60 70 80 20 30 40
Strings use their own CompareTo, so the same class works for text.	`—`	20 30 40 50 60 70 80 20 30 40 apple fig kiwi pear

Cost and common mistakes

Insert is O(h); the full traversal is O(n).

Nested foreach with yield return makes each value pass through one iterator per level of depth. For a very deep tree an explicit stack is faster.
A tree built from sorted input becomes a chain, and operations take O(n). SortedSet<T> in the standard library is a balanced alternative.
CompareTo on null reference values throws. Decide how nulls should be handled before using reference types.

Try it yourself

How would you make the tree sort strings ignoring case?

Reveal answer and reasoning

Accept an IComparer<T> in the constructor and use it instead of CompareTo, for example StringComparer.OrdinalIgnoreCase.

C# generic binary search tree with IEnumerable

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading