A gist to print binary tree in Node.js

tree-printer.js

class TreePrinter {
  constructor() {
    this._maxDigits = 0;
  }

  // BFS: https://en.wikipedia.org/wiki/Breadth-first_search
  // empty node will be null in list
  _getBreadthFirstList(rootNode, maxHeight) {
    const queue = [rootNode];
    const list = [];
    const levelMap = new Map();
    levelMap.set(rootNode, 1);

    while (true) {
      let node = queue.shift();
      const nodeLevel = levelMap.get(node);
      if (nodeLevel > maxHeight) break;
      if (!node.left) {
        node.left = new TreeNode(null);
      }
      if (!node.right) {
        node.right = new TreeNode(null);
      }

      list.push(node.value);
      levelMap.set(node.left, nodeLevel + 1);
      levelMap.set(node.right, nodeLevel + 1);
      queue.push(node.left);
      queue.push(node.right);
    }

    return list;
  }

  _setMaxDigits(list) {
    let maxDigits = 0;
    list.forEach((num) => {
      if (num === null) return;
      const len = num.toString().length;
      if (len > maxDigits) maxDigits = len;
    });
    this._maxDigits = maxDigits;
  }

  // level index is start from 0
  _sortListWithLevel(list) {
    let listWithLevel = [];
    for (let i = 1; i <= list.length; i++) {
      const level = Math.ceil(Math.log2(i + 1));
      const levelIndex = level - 1;
      if (!Array.isArray(listWithLevel[levelIndex])) {
        listWithLevel[levelIndex] = [];
      }
      listWithLevel[levelIndex].push(list[i - 1]);
    }
    listWithLevel = listWithLevel.filter(
      (nodes) => !nodes.every((node) => node === null)
    );
    return listWithLevel;
  }

  _initLeafNodesPosition(nodes) {
    const paddingBetweenDifferenceParent = 3;
    const paddingBetweenSameParent = 1;
    const leftNodeOffset =
      2 + paddingBetweenSameParent + paddingBetweenDifferenceParent;

    let positions = [];
    for (let i = 0; i < nodes.length; i += 2) {
      const start = leftNodeOffset * (i / 2);
      positions[i] = {
        value: nodes[i],
        position: start,
      };
      positions[i + 1] = {
        value: nodes[i + 1],
        position: start + paddingBetweenSameParent + 1,
      };
    }

    return positions;
  }

  _createPositionLevelList(levelList) {
    const leafNodes = levelList[levelList.length - 1];
    const levelPositionList = [this._initLeafNodesPosition(leafNodes)];
    for (let i = levelList.length - 2; i >= 0; i--) {
      const nodes = levelList[i];
      const result = [];
      for (let j = 0; j < nodes.length; j++) {
        const leftChildPosition = levelPositionList[0][2 * j].position;
        const rightPosition = levelPositionList[0][2 * j + 1].position;
        const position =
          leftChildPosition + ((rightPosition - leftChildPosition) >> 1);
        result.push({
          position,
          value: nodes[j],
        });
      }
      levelPositionList.unshift(result);
    }
    return levelPositionList;
  }

  _print(str) {
    process.stdout.write("" + str);
  }

  _printWhiteSpace(length) {
    this._print("".padStart(length * this._maxDigits, " "));
  }

  _printValue(val) {
    if (val === null) {
      this._print("N".padEnd(this._maxDigits, " "));
    } else {
      this._print(val.toString().padEnd(this._maxDigits, " "));
    }
  }

  _printLevel(levelNodes, parentLevelNodes) {
    this._printWhiteSpace(levelNodes[0].position);
    this._printValue(levelNodes[0].value);
    for (let j = 1; j < levelNodes.length; j++) {
      this._printWhiteSpace(
        levelNodes[j].position - levelNodes[j - 1].position - 1
      );
      this._printValue(levelNodes[j].value);
    }
    this._print("\n");
  }

  _printPositionLevelList(positionLevelList) {
    this._printLevel(positionLevelList[0]);
    for (let i = 1; i < positionLevelList.length; i++) {
      this._printLevel(positionLevelList[i], positionLevelList[i - 1]);
    }
  }

  _getMaxHeight(node) {
    if (!node) return 0;
    const leftHeight = this._getMaxHeight(node.left);
    const rightHeight = this._getMaxHeight(node.right);
    const maxChildHeight = Math.max(leftHeight, rightHeight);
    return maxChildHeight + 1;
  }

  printTree(rootNode) {
    const maxHeight = this._getMaxHeight(rootNode);
    const breadthFirstList = this._getBreadthFirstList(rootNode, maxHeight);
    this._setMaxDigits(breadthFirstList);
    const levelList = this._sortListWithLevel(breadthFirstList);
    const positionLevelList = this._createPositionLevelList(levelList);
    this._printPositionLevelList(positionLevelList);
  }
}

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

const treeList = [0, 1, 2, 3, 4, 5, 6, 7, 8].map((val) => new TreeNode(val));

treeList[0].left = treeList[1];
treeList[0].right = treeList[2];

treeList[1].right = treeList[3];
treeList[3].left = treeList[4];
treeList[3].right = treeList[5];

treeList[2].left = treeList[6];
treeList[6].left = treeList[7];

const printer = new TreePrinter();
printer.printTree(treeList[0]);