Huffman Encoding in Javascript

Question

So, I've implemented Huffman Encoding in JavaScript, you can see it live here. Here is the code:

var letters,maxX,maxY,minX,maximumDepth,inputString;
if (typeof Math.log2=="undefined") //Internet Explorer 11
    Math.log2=function(x){
        return Math.log(x)/Math.log(2);
    }
function onButtonClick() {
    inputString=document.getElementById("input").value;
    if (inputString.length<2) {
        alert("Strings of length less than two can't be Huffman encoded.");
        return;
    }
    console.log("Making a Huffman tree for the string \""+inputString+"\".");
    letters=new Object();
    for (let i=0; i<inputString.length; i++) {
        if (letters[inputString[i]]==undefined) {
            letters[inputString[i]]=new Object();
            letters[inputString[i]].frequency=0;
            letters[inputString[i]].hasBeenUsed=false;
            letters[inputString[i]].childrenNodes=[];
        }
        letters[inputString[i]].frequency++;
    }
    var entropy=0,numberOfDistinctLetters=0;
    for (let i in letters) {
        letters[i].probability=letters[i].frequency/inputString.length;
        entropy-=letters[i].probability*Math.log2(letters[i].probability);
        numberOfDistinctLetters++;
    }
    var bitsInEqualCode=Math.ceil(Math.log2(numberOfDistinctLetters));
    if (numberOfDistinctLetters<2) {
        alert("There need to be at least two different symbols!");
        return;
    }
    var howManyUnused=numberOfDistinctLetters;
    var rootNode;
    do {
        let minimum1,minimum2;
        for (let i in letters)
            if (letters[i].hasBeenUsed==false && (minimum1==undefined || letters[i].frequency<letters[minimum1].frequency))
                minimum1=i;
        for (let i in letters)
            if (letters[i].hasBeenUsed==false && i!=minimum1 && (minimum2==undefined || letters[i].frequency<letters[minimum2].frequency))
                minimum2=i;
        console.log("Connecting \'"+minimum1+"\' and \'"+minimum2+"\' into a single node.");
        letters[minimum1].hasBeenUsed=true;
        letters[minimum2].hasBeenUsed=true;
        letters[minimum1+minimum2]=new Object();
        letters[minimum1+minimum2].childrenNodes=[minimum1, minimum2];
        letters[minimum1+minimum2].frequency=letters[minimum1].frequency+letters[minimum2].frequency;
        if (letters[minimum1+minimum2].frequency==inputString.length)
            rootNode=minimum1+minimum2;
        letters[minimum1+minimum2].hasBeenUsed=false;
        howManyUnused=0;
        for (let i in letters)
            if (letters[i].hasBeenUsed==false)
                howManyUnused++;
    }
    while (howManyUnused>1);
    stackWithNodes=[rootNode];
    stackWithCodes=[""];
    stackWithDepths=[0];
    var averageSymbolLength=0;
    maximumDepth=0;
    var counter=0;
    document.getElementById("table").innerHTML="<tr><td>symbol</td><td>frequency</td><td>Huffman code</td><td>equal-length code</td></tr>";
    while (stackWithNodes.length>0) {
        let currentNode=stackWithNodes.pop();
        let currentCode=stackWithCodes.pop();
        let currentDepth=stackWithDepths.pop();
        maximumDepth=Math.max(maximumDepth,currentDepth);
        letters[currentNode].code=currentCode;
        if (letters[currentNode].childrenNodes.length==0) {
            averageSymbolLength+=letters[currentNode].probability*currentCode.length;
            equalLengthCode=counter.toString(2);
            while (equalLengthCode.length<bitsInEqualCode)
                equalLengthCode='0'+equalLengthCode;
            document.getElementById("table").innerHTML+="<tr><td>"+
                                                        currentNode+"</td><td>"+
                                                        letters[currentNode].frequency+"/"+inputString.length+
                                                        "</td><td>"+currentCode+"</td><td>"+equalLengthCode+"</td></tr>";
            counter++;
            continue;
        }
        stackWithNodes.push(letters[currentNode].childrenNodes[0]);
        stackWithNodes.push(letters[currentNode].childrenNodes[1]);
        stackWithCodes.push(currentCode+"0");
        stackWithCodes.push(currentCode+"1");
        stackWithDepths.push(currentDepth+1);
        stackWithDepths.push(currentDepth+1);
    }
    console.log("The Huffman tree is constructed:");
    console.log("node\tfreq\tcode\tleft\tright")
    for (let i in letters)
        console.log("'"+i+"'\t"+letters[i].frequency+"/"+inputString.length+"\t"+
                    letters[i].code+"\t"+((letters[i].childrenNodes[0])?("'"+letters[i].childrenNodes[0]+"'"):"null")+
                    "\t"+(letters[i].childrenNodes[1]?("'"+letters[i].childrenNodes[1]+"'"):"null"));
    console.log("The Huffman encoding is:");
    output="";
    for (let i=0; i<inputString.length; i++)
        output+=letters[inputString[i]].code;
    console.log(output);
    console.log("The average length of a symbol in Huffman code is: "+averageSymbolLength+" bits.");
    document.getElementById("avgLength").innerHTML=averageSymbolLength;
    console.log("The average length of a symbol in the equal-length code is: "+bitsInEqualCode+" bits.");
    document.getElementById("bitsInEqualCode").innerHTML=bitsInEqualCode;
    console.log("The entropy of the input string is: "+entropy+" bits.");
    document.getElementById("entropy").innerHTML=entropy;
    console.log("The efficiency of the Huffman code is: "+(entropy/averageSymbolLength));
    console.log("The efficiency of the equal-length code is: "+(entropy/bitsInEqualCode));
    document.getElementById("output").innerText=output;
    var tree=document.getElementById("tree");
    var svgNS=tree.namespaceURI;
    while (document.getElementById("tree").childNodes.length) //Clear the diagram ("innerHTML" won't work because... SVG).
        document.getElementById("tree").removeChild(document.getElementById("tree").firstChild);
    maxX=maxY=minX=0;
    draw(rootNode,0,0,30*Math.pow(2,maximumDepth),0);
    for (let i = 0; i < document.getElementById("tree").childNodes.length; i++) //In case a node falls left of the diagram, move all nodes rightwards.
    {
        if (document.getElementById("tree").childNodes[i].getAttribute("x"))
            document.getElementById("tree").childNodes[i].setAttribute("x", document.getElementById("tree").childNodes[i].getAttribute("x") * 1 - minX);
        if (document.getElementById("tree").childNodes[i].getAttribute("x1"))
            document.getElementById("tree").childNodes[i].setAttribute("x1", document.getElementById("tree").childNodes[i].getAttribute("x1") * 1 - minX);
        if (document.getElementById("tree").childNodes[i].getAttribute("x2"))
            document.getElementById("tree").childNodes[i].setAttribute("x2", document.getElementById("tree").childNodes[i].getAttribute("x2") * 1 - minX);
    }
    document.getElementById("tree").style.height = maxY + 100 + "px";
    document.getElementById("tree").style.width= maxX - minX + 100 + "px";
    document.getElementById("diagramSpan").scrollLeft = document.getElementById("node0").getAttribute("x") - document.getElementById("diagramSpan").clientWidth / 2 + 75; //The root of the tree will be in the center of the screen.
}
function draw(nodeName, x, y, space, id)
{
    if (x > maxX)
        maxX = x;
    if (x < minX)
        minX = x;
    if (y > maxY)
        maxY = y;
    var svgNS = document.getElementById("tree").namespaceURI;
    var rectangle = document.createElementNS(svgNS, "rect");
    rectangle.setAttribute("x", x);
    rectangle.setAttribute("y", y);
    rectangle.setAttribute("width", 50);
    rectangle.setAttribute("height", 50);
    rectangle.setAttribute("id", "node" + id);
    rectangle.setAttribute("fill","#EEEEEE");
    document.getElementById("tree").appendChild(rectangle);
    var text = document.createElementNS(svgNS, "text");
    text.appendChild(document.createTextNode(letters[nodeName].frequency+"/"+inputString.length));
    text.setAttribute("x", x+5);
    text.setAttribute("y", y + 20);
    text.style.fill = "black";
    text.setAttribute("font-family", "monospace");
    text.setAttribute("font-size", 14);
    document.getElementById("tree").appendChild(text); 
    if (nodeName.length==1) {
        let character = document.createElementNS(svgNS, "text");
        character.appendChild(document.createTextNode(nodeName));
        character.setAttribute("x", x+20);
        character.setAttribute("y", y + 40);
        character.style.fill = "black";
        character.setAttribute("font-family", "monospace");
        character.setAttribute("font-size", 14);
        document.getElementById("tree").appendChild(character);
    }
    for (let i = 0; i < letters[nodeName].childrenNodes.length; i++) {
        draw(letters[nodeName].childrenNodes[i], x + (i - 0.5) * space, y + 100, space / 2, id + 1);
        let line = document.createElementNS(svgNS, "line");
        line.setAttribute("x1", x + 25);
        line.setAttribute("y1", y + 50);
        line.setAttribute("x2", x + (i - 0.5) * space + 25);
        line.setAttribute("y2", y + 100);
        line.setAttribute("stroke-width", 2);
        line.setAttribute("stroke", "black");
        document.getElementById("tree").appendChild(line);
        let bit = document.createElementNS(svgNS,"text");
        bit.appendChild(document.createTextNode(i));
        bit.setAttribute("x", x + (i - 0.5) * space + 25);
        bit.setAttribute("y", y + 80);
        bit.style.fill = "black";
        bit.setAttribute("font-family", "monospace");
        bit.setAttribute("font-size", 14);
        document.getElementById("tree").appendChild(bit);
    }
}

A sample HTML that uses it (I know it can be made a lot better) is:

<!doctype html>
<html lang="en">
    <head>
        <title>Huffman Encoding in JavaScript</title>
        <script src="huffman.js"></script>
        <style>
            table,th,td {
                border:1px black solid;
            }
        </style>
    </head>
    <body>
        Enter the string here:<br/>
        <input type="text" id="input" value="TEO SAMARZIJA"/>
        <button onclick="onButtonClick()">Encode!</button><br/>
        The Huffman encoded string is: <span id="output" style="font-family:monospace"></span><br/>
        <span id="diagramSpan" style="display:block; width:100%; height:50%; overflow:scroll">
            <svg id="tree">
            </svg>
        </span><br/>
        <table id="table"></table><br/>
        The average length of a symbol in the Huffman code is <span id="avgLength">0</span> bits.<br/>
        The average length of a symbol in the equal-length code is <span id="bitsInEqualCode">0</span> bits.<br/>
        The entropy of the input string is <span id="entropy">0</span> bits.<br/>
    </body>
</html>

So, what do you think about it?

Answer 1

You have

<button onclick="onButtonClick()">Encode!</button>

Better to avoid inline handlers in a modern codebase, they have too many problems to be worth using. Attach the listener properly in the Javascript by using addEventListener instead.

Consider always strict mode to reduce silent bugs. For example, you never define the stackWithNodes, stackWithCodes, stackWithDepths, output, and some other variables, so they're implicitly global, which is not a good idea. Always declare variables before using them. Strict mode will throw an error when an undeclared variable is used, allowing you to fix it immediately (rather than it causing a hard-to-identify bug down the line).

If you're going to use ES2015 syntax like let in the code, great (it often makes code shorter and more readable!) - but if you're going to use ES2015 syntax, best to use it everywhere - avoid var. Only use let when you must reassign the variable - otherwise, use const.

You declare a bunch of global variables shared between onButtonClick and draw:

var letters, maxX, maxY, minX, maximumDepth;

If you want to communicate data between functions, it would be more appropriate to pass arguments instead.

letters = new Object();

If you want to create an empty object, just use {} - using the Object constructor is verbose and weird.

Rather than iterating over the string manually with:

for (let i = 0; i < inputString.length; i++) {
  if (letters[inputString[i]] == undefined) {
    letters[inputString[i]] = new Object();
    letters[inputString[i]].frequency = 0;
    letters[inputString[i]].hasBeenUsed = false;
    letters[inputString[i]].childrenNodes = [];
  }
  letters[inputString[i]].frequency++;
}

Since we can use ES2015, using for..of wll make the code a lot cleaner - no manual iteration required, and no having to mess with indicies. You can also assign the whole object all at once, rather than first creating an object, then assigning to its keys. (See next code block after this one for an example.) You also have:

for (let i in letters) {
  letters[i].probability = letters[i].frequency / inputString.length;
  entropy -= letters[i].probability * Math.log2(letters[i].probability);
  numberOfDistinctLetters++;
}

You don't care at all what the i is (the character), so iterating over the keys with in doesn't make much sense. If all you care about is the values, use Object.values instead. Rather than incrementing numberOfDistinctLetters each time, it would be clearer to assign it to its final value immediately, by checking the number of values in the object. This would also be a nice thing to put into a standalone function, to make the onbuttonclick less bulky. The creation of the entropy number is not tied to the assignment of the probabilities to each letter object, so best to separate them. The assignment to the probabilities can go in the function that creates the letter object.

const constructLettersObj = (inputString) => {
  const lettersObj = {};
  for (const char of inputString) {
    if (!lettersObj[char]) {
      lettersObj[char] = {
        frequency: 0,
        hasBeenUsed: false,
        childrenNodes: [],
      };
    }
    lettersObj[char].frequency++;
  }
  for (const letterObj of Object.values(lettersObj)) {
    letterObj.probability = letterObj.frequency / inputString.length;
  }
  return lettersObj;
};

If you did want to stick with the for..in loop for whatever reaason, don't name the character i (i is generally understood to be a numeric index, but characters aren't numeric), and make sure to declare it with const, not let, since you aren't reassigning the variable. Maybe call it char instead of i. You use that same pattern various other places in the code - to keep the code clean, if you only need to iterate over object values, but not keys, then use Object.values.

Once the above letters object has been constructed, you can create the entropy number by mapping to the probabilities multiplied by the logarithm, then summing them all together with .reduce:

const entropy = vals
  .map(({ probability }) => probability * Math.log2(probability))
  .reduce((a, b) => a + b);

This way, you can declare entropy with const, no reassignment or generic looping required, and its value will be easier to determine at a glance by a reader.

While connecting the nodes together, you do:

for (let i in lettersObj)
  if (lettersObj[i].hasBeenUsed == false && (minimum1 == undefined || lettersObj[i].frequency < lettersObj[minimum1].frequency))
    minimum1 = i;
for (let i in lettersObj)
  if (lettersObj[i].hasBeenUsed == false && i != minimum1 && (minimum2 == undefined || lettersObj[i].frequency < lettersObj[minimum2].frequency))
    minimum2 = i;
console.log("Connecting \'" + minimum1 + "\' and \'" + minimum2 + "\' into a single node.");
lettersObj[minimum1].hasBeenUsed = true;
lettersObj[minimum2].hasBeenUsed = true;
lettersObj[minimum1 + minimum2] = new Object();
lettersObj[minimum1 + minimum2].childrenNodes = [minimum1, minimum2];
lettersObj[minimum1 + minimum2].frequency = lettersObj[minimum1].frequency + lettersObj[minimum2].frequency;
if (lettersObj[minimum1 + minimum2].frequency == inputString.length)
  rootNode = minimum1 + minimum2;
lettersObj[minimum1 + minimum2].hasBeenUsed = false;
howManyUnused = 0;
for (const i in lettersObj)
  if (lettersObj[i].hasBeenUsed == false)
    howManyUnused++;

You can clean this up the same way as above - initialize the lettersObj[minimum1 + minimum2] with an object literal instead, and i should probably be renamed to char (since it's a character, not an index), and since it doesn't get reassigned, declare it with const Always use === and !== to compare - don't use == or !=, it has strange rules that developers are better off not having to memorize. Or, since the minimums will always be characters, a simple truthy test would also be enough. To iterate over both the object's values and keys at once, use Object.entries. Save the minimum1 + minimum2 in a variable instead of repeating the calculation multiple times - write DRY code:

for (const [char, letterObj] of Object.entries(lettersObj))
  if (!letterObj.hasBeenUsed && (!minimum1 || letterObj.frequency < lettersObj[minimum1].frequency))
    minimum1 = char;
for (const [char, letterObj] of Object.entries(lettersObj))
  if (!letterObj.hasBeenUsed && char != minimum1 && (!minimum2 || letterObj.frequency < lettersObj[minimum2].frequency))
    minimum2 = char;
console.log("Connecting \'" + minimum1 + "\' and \'" + minimum2 + "\' into a single node.");
lettersObj[minimum1].hasBeenUsed = true;
lettersObj[minimum2].hasBeenUsed = true;
lettersObj[minimum1 + minimum2] = {
  childrenNodes: [minimum1, minimum2],
  frequency: lettersObj[minimum1].frequency + lettersObj[minimum2].frequency,
};
const combinedKey = minimum1 + minimum2;
if (lettersObj[combinedKey].frequency == inputString.length)
  rootNode = combinedKey;
lettersObj[combinedKey].hasBeenUsed = false;
howManyUnused = Object.values(lettersObj)
  .reduce((a, letterObj) => a + !letterObj.hasBeenUsed, 0);

On a similar note, for the code to be DRY, don't select elements over and over again, like with:

while (document.getElementById("tree").childNodes.length) //Clear the diagram ("innerHTML" won't work because... SVG).
  document.getElementById("tree").removeChild(document.getElementById("tree").firstChild);
maxX = maxY = minX = 0;
draw(rootNode, 0, 0, 30 * Math.pow(2, maximumDepth), 0, inputString.length, lettersObj);
for (let i = 0; i < document.getElementById("tree").childNodes.length; i++) //In case a node falls left of the diagram, move all nodes rightwards.
{
  if (document.getElementById("tree").childNodes[i].getAttribute("x"))
    document.getElementById("tree").childNodes[i].setAttribute("x", document.getElementById("tree").childNodes[i].getAttribute("x") * 1 - minX);
  if (document.getElementById("tree").childNodes[i].getAttribute("x1"))
    document.getElementById("tree").childNodes[i].setAttribute("x1", document.getElementById("tree").childNodes[i].getAttribute("x1") * 1 - minX);
  if (document.getElementById("tree").childNodes[i].getAttribute("x2"))
    document.getElementById("tree").childNodes[i].setAttribute("x2", document.getElementById("tree").childNodes[i].getAttribute("x2") * 1 - minX);
}
document.getElementById("tree").style.height = maxY + 100 + "px";
document.getElementById("tree").style.width = maxX - minX + 100 + "px";
document.getElementById("diagramSpan").scrollLeft = document.getElementById("node0").getAttribute("x") - document.getElementById("diagramSpan").clientWidth / 2 + 75; //The root of the tree will be in the center of the screen.

Select elements once and save them in a variable. Also, .childNodes will iterate over text nodes too, which is not desirable - if you ever had text nodes, they would cause problems. Because you only want to iterate over elements, use .children instead - and instead of iterating manually, invoke the HTMLCollection's iterator instead. When you want to check if an element has an attribute, it's most appropriate to use hasAttribute (not getAttribute):

const tree = document.getElementById("tree");
for (const child of tree.children) {
  child.remove();
}
maxX = maxY = minX = 0;
draw(rootNode, 0, 0, 30 * Math.pow(2, maximumDepth), 0, inputString.length, lettersObj);
// In case a node falls left of the diagram, move all nodes rightwards:
for (const child of tree.children) {
  if (child.hasAttribute("x"))
    child.setAttribute("x", child.getAttribute("x") * 1 - minX);
  if (child.hasAttribute("x1"))
    child.setAttribute("x1", child.getAttribute("x1") * 1 - minX);
  if (child.hasAttribute("x2"))
    child.setAttribute("x2", child.getAttribute("x2") * 1 - minX);
}
tree.style.height = maxY + 100 + "px";
tree.style.width = maxX - minX + 100 + "px";
const diagramSpan = document.getElementById("diagramSpan");
diagramSpan.scrollLeft = document.getElementById("node0").getAttribute("x") - diagramSpan.clientWidth / 2 + 75;

The draw function is a bit long and difficult to read. You can make it much nicer by typing HTML markup directly instead of large numbers of setAttribute calls. (You wouldn't do this when you might be concatenating untrusted input, but it's fine when you know exactly what sort of things are being interpolated.) You can do it like this:

const lineHTML = `
  <line
    x1=${x + 25}
    y1=${y + 50}
    x2=${x + (i - 0.5) * space + 25}
    y2=${y + 100}
    strike-width=2
    stroke=black
  ></line>
`;
tree.insertAdjacentHTML('beforeend', lineHTML);

You can follow the same pattern in the various places where you have to create elements with lots of attributes.

There are lots of other improvements that can be made, but this should be a good start.

You should strongly consider using a linter which will automatically prompt you to fix many of these potential mistakes/code smells.

Live demo of the mostly-fixed code:

'use strict';

let maxX, maxY, minX, maximumDepth;

const constructLettersObj = (inputString) => {
  const lettersObj = {};
  for (const char of inputString) {
    if (!lettersObj[char]) {
      lettersObj[char] = {
        frequency: 0,
        hasBeenUsed: false,
        childrenNodes: [],
      };
    }
    lettersObj[char].frequency++;
  }
  for (const letterObj of Object.values(lettersObj)) {
    letterObj.probability = letterObj.frequency / inputString.length;
  }
  return lettersObj;
};

function onButtonClick() {
  const inputString = document.getElementById("input").value;
  if (inputString.length < 2) {
    alert("Strings of length less than two can't be Huffman encoded.");
    return;
  }
  console.log("Making a Huffman tree for the string \"" + inputString + "\".");
  const lettersObj = constructLettersObj(inputString);
  const vals = Object.values(lettersObj);
  const numberOfDistinctLetters = vals.length;
  if (numberOfDistinctLetters < 2) {
    alert("There need to be at least two different symbols!");
    return;
  }
  const entropy = vals
    .map(({ probability }) => probability * Math.log2(probability))
    .reduce((a, b) => a + b);
  const bitsInEqualCode = Math.ceil(Math.log2(numberOfDistinctLetters));
  
  let howManyUnused = numberOfDistinctLetters;
  let rootNode;
  do {
    let minimum1, minimum2;
    for (const [char, letterObj] of Object.entries(lettersObj))
      if (!letterObj.hasBeenUsed && (!minimum1 || letterObj.frequency < lettersObj[minimum1].frequency))
        minimum1 = char;
    for (const [char, letterObj] of Object.entries(lettersObj))
      if (!letterObj.hasBeenUsed && char != minimum1 && (!minimum2 || letterObj.frequency < lettersObj[minimum2].frequency))
        minimum2 = char;
    console.log("Connecting \'" + minimum1 + "\' and \'" + minimum2 + "\' into a single node.");
    lettersObj[minimum1].hasBeenUsed = true;
    lettersObj[minimum2].hasBeenUsed = true;
    const combinedKey = minimum1 + minimum2;
    lettersObj[combinedKey] = {
      childrenNodes: [minimum1, minimum2],
      frequency: lettersObj[minimum1].frequency + lettersObj[minimum2].frequency,
    };
    if (lettersObj[combinedKey].frequency == inputString.length)
      rootNode = combinedKey;
    lettersObj[combinedKey].hasBeenUsed = false;
    howManyUnused = Object.values(lettersObj)
      .reduce((a, letterObj) => a + !letterObj.hasBeenUsed, 0);
  }
  while (howManyUnused > 1);
  const stackWithNodes = [rootNode];
  const stackWithCodes = [""];
  const stackWithDepths = [0];
  let averageSymbolLength = 0;
  maximumDepth = 0;
  let counter = 0;
  document.getElementById("table").innerHTML = "<tr><td>symbol</td><td>frequency</td><td>Huffman code</td><td>equal-length code</td></tr>";
  while (stackWithNodes.length > 0) {
    const currentNode = stackWithNodes.pop();
    const currentCode = stackWithCodes.pop();
    const currentDepth = stackWithDepths.pop();
    maximumDepth = Math.max(maximumDepth, currentDepth);
    lettersObj[currentNode].code = currentCode;
    if (lettersObj[currentNode].childrenNodes.length == 0) {
      averageSymbolLength += lettersObj[currentNode].probability * currentCode.length;
      let equalLengthCode = counter.toString(2);
      while (equalLengthCode.length < bitsInEqualCode)
        equalLengthCode = '0' + equalLengthCode;
      document.getElementById("table").innerHTML += "<tr><td>" +
        currentNode + "</td><td>" +
        lettersObj[currentNode].frequency + "/" + inputString.length +
        "</td><td>" + currentCode + "</td><td>" + equalLengthCode + "</td></tr>";
      counter++;
      continue;
    }
    stackWithNodes.push(lettersObj[currentNode].childrenNodes[0]);
    stackWithNodes.push(lettersObj[currentNode].childrenNodes[1]);
    stackWithCodes.push(currentCode + "0");
    stackWithCodes.push(currentCode + "1");
    stackWithDepths.push(currentDepth + 1);
    stackWithDepths.push(currentDepth + 1);
  }
  console.log("The Huffman tree is constructed:");
  console.log("node\tfreq\tcode\tleft\tright")
  for (const i in lettersObj)
    console.log("'" + i + "'\t" + lettersObj[i].frequency + "/" + inputString.length + "\t" +
      lettersObj[i].code + "\t" + ((lettersObj[i].childrenNodes[0]) ? ("'" + lettersObj[i].childrenNodes[0] + "'") : "null") +
      "\t" + (lettersObj[i].childrenNodes[1] ? ("'" + lettersObj[i].childrenNodes[1] + "'") : "null"));
  console.log("The Huffman encoding is:");
  let output = "";
  for (let i = 0; i < inputString.length; i++)
    output += lettersObj[inputString[i]].code;
  console.log(output);
  console.log("The average length of a symbol in Huffman code is: " + averageSymbolLength + " bits.");
  document.getElementById("avgLength").innerHTML = averageSymbolLength;
  console.log("The average length of a symbol in the equal-length code is: " + bitsInEqualCode + " bits.");
  document.getElementById("bitsInEqualCode").innerHTML = bitsInEqualCode;
  console.log("The entropy of the input string is: " + entropy + " bits.");
  document.getElementById("entropy").innerHTML = entropy;
  console.log("The efficiency of the Huffman code is: " + (entropy / averageSymbolLength));
  console.log("The efficiency of the equal-length code is: " + (entropy / bitsInEqualCode));
  document.getElementById("output").innerText = output;
  const tree = document.getElementById("tree");
  for (const child of tree.children) {
    child.remove();
  }
  maxX = maxY = minX = 0;
  draw(rootNode, 0, 0, 30 * Math.pow(2, maximumDepth), 0, inputString.length, lettersObj);
  // In case a node falls left of the diagram, move all nodes rightwards:
  for (const child of tree.children) {
    if (child.hasAttribute("x"))
      child.setAttribute("x", child.getAttribute("x") * 1 - minX);
    if (child.hasAttribute("x1"))
      child.setAttribute("x1", child.getAttribute("x1") * 1 - minX);
    if (child.hasAttribute("x2"))
      child.setAttribute("x2", child.getAttribute("x2") * 1 - minX);
  }
  tree.style.height = maxY + 100 + "px";
  tree.style.width = maxX - minX + 100 + "px";
  const diagramSpan = document.getElementById("diagramSpan");
  diagramSpan.scrollLeft = document.getElementById("node0").getAttribute("x") - diagramSpan.clientWidth / 2 + 75; //The root of the tree will be in the center of the screen.
}

function draw(nodeName, x, y, space, id, inputLength, lettersObj) {
  if (x > maxX)
    maxX = x;
  if (x < minX)
    minX = x;
  if (y > maxY)
    maxY = y;
  const svgNS = document.getElementById("tree").namespaceURI;
  const rectangle = document.createElementNS(svgNS, "rect");
  rectangle.setAttribute("x", x);
  rectangle.setAttribute("y", y);
  rectangle.setAttribute("width", 50);
  rectangle.setAttribute("height", 50);
  rectangle.setAttribute("id", "node" + id);
  rectangle.setAttribute("fill", "#EEEEEE");
  document.getElementById("tree").appendChild(rectangle);
  const text = document.createElementNS(svgNS, "text");
  text.innerHTML = lettersObj[nodeName].frequency + "/" + inputLength;
  text.setAttribute("x", x + 5);
  text.setAttribute("y", y + 20);
  text.style.fill = "black";
  text.setAttribute("font-family", "monospace");
  text.setAttribute("font-size", 14);
  document.getElementById("tree").appendChild(text);
  if (nodeName.length == 1) {
    const character = document.createElementNS(svgNS, "text");
    character.innerHTML = nodeName;
    character.setAttribute("x", x + 20);
    character.setAttribute("y", y + 40);
    character.style.fill = "black";
    character.setAttribute("font-family", "monospace");
    character.setAttribute("font-size", 14);
    document.getElementById("tree").appendChild(character);
  }
  for (let i = 0; i < lettersObj[nodeName].childrenNodes.length; i++) {
    draw(lettersObj[nodeName].childrenNodes[i], x + (i - 0.5) * space, y + 100, space / 2, id + 1, inputLength, lettersObj);
    const str = `
    <line
      x1=${x + 25}
      y1=${y + 50}
      x2=${x + (i - 0.5) * space + 25}
      y2=${y + 100}
      strike-width=2
      stroke=black
    ></line>
    `;
    tree.insertAdjacentHTML('beforeend', str);
    const bitHTML = `
      <text
        x=${x + (i - 0.5) * space + 25}
        y=${y + 80}
        style="fill: black;"
        font-family=monospace
        font-size=14
      >${i}</text>
    `;
    tree.insertAdjacentHTML('beforeend', bitHTML);
  }
}

table,
th,
td {
  border: 1px black solid;
}

Enter the string here:<br/>
<input type="text" id="input" value="TEO SAMARZIJA" />
<button onclick="onButtonClick()">Encode!</button><br/> The Huffman encoded string is: <span id="output" style="font-family:monospace"></span><br/>
<span id="diagramSpan" style="display:block; width:100%; height:50%; overflow:scroll">
            <svg id="tree">
            </svg>
        </span><br/>
<table id="table"></table><br/> The average length of a symbol in the Huffman code is <span id="avgLength">0</span> bits.<br/> The average length of a symbol in the equal-length code is <span id="bitsInEqualCode">0</span> bits.<br/> The entropy of the input string is
<span id="entropy">0</span> bits.<br/>

Answer 2

I agree with the many great points already mentioned by CertainPerformance - especially ES6 features. There are a few other aspects mentioned below.

Brackets

There are lines with no braces/brackets - e.g.

for (let i=0; i<inputString.length; i++)

    output+=letters[inputString[i]].code;

and

    if (document.getElementById("tree").childNodes[i].getAttribute("x"))

        document.getElementById("tree").childNodes[i].setAttribute("x", document.getElementById("tree").childNodes[i].getAttribute("x") * 1 - minX);
    if (document.getElementById("tree").childNodes[i].getAttribute("x1"))
        document.getElementById("tree").childNodes[i].setAttribute("x1", document.getElementById("tree").childNodes[i].getAttribute("x1") * 1 - minX);
    if (document.getElementById("tree").childNodes[i].getAttribute("x2"))
        document.getElementById("tree").childNodes[i].setAttribute("x2", document.getElementById("tree").childNodes[i].getAttribute("x2") * 1 - minX);

It is a better practice to use braces even on single-line if-else statements. Not doing so can sometimes lead to freaky bugs.

Alerts

There are two places alert() is called (in onButtonClick()). Some users may have disabled alerts in a browser setting. It is better to use HTML5 <dialog> element - it allows more control over the style and doesn't block the browser. It is now supported by all major browsers.

Numbers in draw()

There are various numbers used in calculations in the draw() function - e.g. 50, 40, 25, 20, 100, etc.. Presumably those are for widths, heights, etc. It would be wise to store those as constants so if you need to update the values you can do it in one place.