type Node = {
  char?: string;
  freq: number;
  left?: Node;
  right?: Node;
};

export function huffmanCodes(pairs: [string, number][]): Record<string, string> {

  if (pairs.length === 1) {
    return { [pairs[0][0]]: "0" };
  }

  let nodes: Node[] = pairs.map(([char, freq]) => ({ char, freq }));

  while (nodes.length > 1) {
    nodes.sort((a, b) => a.freq - b.freq);

    const left = nodes.shift()!;
    const right = nodes.shift()!;

    nodes.push({
      freq: left.freq + right.freq,
      left,
      right,
    });
  }

  const result: Record<string, string> = {};

  function traverse(node: Node, path: string) {
    if (node.char !== undefined) {
      result[node.char] = path;
      return;
    }

    traverse(node.left!, path + "0");
    traverse(node.right!, path + "1");
  }

  traverse(nodes[0], "");

  return result;
}