1
/**
2
 * @param {TreeNode} root
3
 * @return {string[][]}
4
 */
5
var printTree = function (root) {
6
  // find the height of the tree
7
  const m = getHeight(root);
8
  const height = m - 1;
9
  const n = 2 ** (height + 1) - 1;
10
  // create an empty m by n matrix
11
  const ans = [];
12
  for (let i = 0; i < m; i++) {
13
    ans.push(Array(n).fill(""));
14
  }
15
  // insert the root
16
  ans[0][(n - 1) / 2] = root.val.toString();
17
  // insert the rest of the nodes
18
  format(root, 0, (n - 1) / 2, ans, height);
19
  return ans;
20
};
21

22
function getHeight(node) {
23
  if (!node) return 0;
24
  const leftHeight = getHeight(node.left) + 1;
25
  const rightHeight = getHeight(node.right) + 1;
26
  return Math.max(leftHeight, rightHeight); // take the subtree with bigger height
27
}
28

29
function format(node, r, c, ans, height) {
30
  const offset = 2 ** (height - r - 1); // calculate the common offset
31
  if (node.left) {
32
    ans[r + 1][c - offset] = node.left.val.toString();
33
    format(node.left, r + 1, c - offset, ans, height); // recurse left node
34
  }
35
  if (node.right) {
36
    ans[r + 1][c + offset] = node.right.val.toString();
37
    format(node.right, r + 1, c + offset, ans, height); // recurse right node
38
  }
39
}