Skip to content

Instantly share code, notes, and snippets.

@clinyong
Last active May 8, 2022 04:16
Show Gist options
  • Save clinyong/8f5b591073305e3cf4f17ac2ecbfd99d to your computer and use it in GitHub Desktop.
Save clinyong/8f5b591073305e3cf4f17ac2ecbfd99d to your computer and use it in GitHub Desktop.
A gist to print binary tree in Node.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]);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment