Huffman Encoding

Huffman

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

namespace huffman
{
	public class Huffman
	{
		public Huffman ()
		{
		}

		public string Encode(string toEncode){

			var frequencies = GetFrequencies(toEncode);
			var initialTree = frequencies.Values.ToList();

			var tree = GetTree(initialTree);

			var result = new StringBuilder();

			foreach (var x in toEncode) {
				result.Append(GetCharEncoding(x.ToString(), tree));
			}

			return result.ToString();
		}

		private string GetCharEncoding(string x, Node huffmanTree){
			if (huffmanTree.Character.Length == 1 && huffmanTree.Character == x)
				return string.Empty;
			else if (huffmanTree.left.Character.Contains (x))
				return "0" + GetCharEncoding (x, huffmanTree.left);
			else
				return "1"+ GetCharEncoding (x, huffmanTree.right);
		}

		private Dictionary<char,Node> GetFrequencies(string toEncode){
			Dictionary<char,Node> nodeFrequency = new Dictionary<char, Node> ();

			foreach (var x in toEncode) {
				if (nodeFrequency.ContainsKey (x))
					nodeFrequency [x].Frequency++;
				else
					nodeFrequency [x] = new Node (){ Frequency = 1, Character = x.ToString() };
			}

			return nodeFrequency;
		}

		private Node GetTree(List<Node>nodes){

			nodes.Sort();
			if (nodes.Count == 0)
				return null;
			else if (nodes.Count == 1)
				return nodes[0];

			var min = nodes [0];
			var secondMin = nodes [1];

			nodes.RemoveAt (0);//Remove First
			nodes.RemoveAt (0);//Remove First

			nodes.Insert(0, new Node(){Character = min.Character+secondMin.Character,Frequency = min.Frequency + secondMin.Frequency, left = min, right = secondMin});

			return GetTree(nodes);
		}
	}

	public class Node:IComparable{

		public int CompareTo (object obj)
		{
			var x = (Node)obj;
			return this.Frequency.CompareTo (x.Frequency);
		}



		public string Character{get;set;}
		public Node left;
		public Node right;
		public int Frequency{ get; set; }
	}
}