Print Binary Tree

medium tree dfs

Problem

Format a binary tree into a 2D string array of (height+1) rows.

Inputroot = [1,2,3,null,4]

Output[['','','','1','','',''], ...]

Each level halves the horizontal stride.

input

def print_tree(root):
    def height(n): return 0 if not n else 1 + max(height(n.left), height(n.right))
    h = height(root); cols = (1 << h) - 1
    grid = [[''] * cols for _ in range(h)]
    def fill(n, r, l, r2):
        if not n: return
        m = (l + r2) // 2
        grid[r][m] = str(n.val)
        fill(n.left, r + 1, l, m - 1)
        fill(n.right, r + 1, m + 1, r2)
    fill(root, 0, 0, cols - 1)
    return grid

function printTree(root) {
  const height = n => n ? 1 + Math.max(height(n.left), height(n.right)) : 0;
  const h = height(root); const cols = (1 << h) - 1;
  const grid = Array.from({length: h}, () => new Array(cols).fill(''));
  const fill = (n, r, l, r2) => {
    if (!n) return;
    const m = (l + r2) >> 1;
    grid[r][m] = String(n.val);
    fill(n.left, r + 1, l, m - 1); fill(n.right, r + 1, m + 1, r2);
  };
  fill(root, 0, 0, cols - 1);
  return grid;
}

List> printTree(TreeNode root) {
    int h = height(root); int cols = (1 << h) - 1;
    List> grid = new ArrayList<>();
    for (int i = 0; i < h; i++) {
        List row = new ArrayList<>();
        for (int j = 0; j < cols; j++) row.add("");
        grid.add(row);
    }
    fill(root, 0, 0, cols - 1, grid);
    return grid;
}
int height(TreeNode n) { return n == null ? 0 : 1 + Math.max(height(n.left), height(n.right)); }
void fill(TreeNode n, int r, int l, int r2, List> g) {
    if (n == null) return;
    int m = (l + r2) / 2;
    g.get(r).set(m, String.valueOf(n.val));
    fill(n.left, r + 1, l, m - 1, g);
    fill(n.right, r + 1, m + 1, r2, g);
}

int height(TreeNode* n) { return !n ? 0 : 1 + max(height(n->left), height(n->right)); }
void fill(TreeNode* n, int r, int l, int r2, vector>& g) {
    if (!n) return;
    int m = (l + r2) / 2;
    g[r][m] = to_string(n->val);
    fill(n->left, r + 1, l, m - 1, g);
    fill(n->right, r + 1, m + 1, r2, g);
}
vector> printTree(TreeNode* root) {
    int h = height(root); int cols = (1 << h) - 1;
    vector> g(h, vector(cols, ""));
    fill(root, 0, 0, cols - 1, g);
    return g;
}

Explanation

We want to draw the tree into a 2D grid of strings so it looks balanced. The key insight is that each row is a tree level, and each node sits in the exact horizontal middle of the column range it owns.

First we measure the tree's height h with a tiny recursive helper. A tree of height h needs cols = 2^h - 1 columns so that every level has room to spread out without overlap.

Then a recursive fill(n, r, l, r2) places node n at row r, in the middle column m = (l + r2) / 2 of the slice [l, r2] it controls. The left child recurses into the left half [l, m-1] and the right child into the right half [m+1, r2], one row deeper.

Example: [1, 2, 3, null, 4] has height 3, so 7 columns. Root 1 lands at column 3 (the center). Node 2 takes columns [0..2] and sits at column 1; node 3 takes [4..6] and sits at column 5; node 4 is under 2 at column 2.

Every empty cell stays a blank string. Because each node halves the column range as it descends, the picture comes out perfectly centered.

Time: O(n + 2^h) Space: O(h · 2^h)