Print Binary Tree: Level-by-Level Grid Placement

LeetCode Print Binary Tree (Problem 655) asks you to represent a binary tree as a 2D string grid. Each node gets placed at a specific row and column, and all empty positions are filled with empty strings. The challenge is figuring out the right grid dimensions and the exact column for each node.

The problem

You are given the root of a binary tree. Return a 2D list of strings representing the tree. The grid has height + 1 rows and 2^(height+1) - 1 columns, where height is the height of the tree (0-indexed). The root goes in the middle of the top row, and each child is offset from its parent by a power of 2 that decreases with each level.

For example, the tree [1, 2, 3, null, 4] produces a 3x7 grid where node 1 sits at position [0][3], node 2 at [1][1], node 3 at [1][5], and node 4 at [2][2].

Why recursive grid placement works

You might think about doing a level-order traversal, but the tricky part is not visiting nodes in order. It is computing where each node belongs in the grid. The column positions follow a recursive halving pattern that maps naturally onto a DFS approach.

The root always sits at the center column of the grid. Its left child shifts left by half the remaining space, and its right child shifts right by the same amount. At each deeper level, the offset halves again. This is exactly what 2^(height - level - 1) computes: at level 0, the offset is large (half the grid width), and at the deepest level, the offset is 0.

A recursive function that carries the current row and column is the cleanest way to express this. At each node, you write the node's value into the grid, then recurse left with col - offset and right with col + offset.

Step-by-step walkthrough

A few things to notice:

• The grid dimensions are fully determined by the tree height. You compute height first, then allocate the grid.
• The root column is always 2^height - 1, which is the middle index of a row with 2^(height+1) - 1 columns.
• Each recursive call just passes the current row, column, and the node. The offset is derived from the row and the height.

The code

def printTree(root):
    def height(node):
        if not node:
            return -1
        return 1 + max(height(node.left), height(node.right))

    h = height(root)
    rows = h + 1
    cols = (1 << (h + 1)) - 1
    grid = [[""] * cols for _ in range(rows)]

    def fill(node, r, c):
        if not node:
            return
        grid[r][c] = str(node.val)
        offset = 1 << (h - r - 1)
        fill(node.left, r + 1, c - offset)
        fill(node.right, r + 1, c + offset)

    fill(root, 0, (1 << h) - 1)
    return grid

The height function returns the 0-indexed height of the tree (a single node has height 0, an empty tree returns -1). With the height known, you compute the grid dimensions: h + 1 rows and 2^(h+1) - 1 columns. The fill function does a preorder traversal, writing each node's value at the correct (r, c) position and recursing with updated offsets.

Complexity analysis

The grid has (h + 1) rows and 2^(h+1) - 1 columns. Initializing it takes O(rows * cols) time. The recursive fill visits each node exactly once, which is O(n), but the grid size dominates since it can be much larger than n for sparse trees. Space is also O(rows * cols) for the output grid itself.

The building blocks

Column offset as power-of-two halving

The pattern of halving the offset at each level is the same structure you see in binary search: you start with a range and cut it in half at each step. Here, the "range" is the horizontal space available for a subtree. The root gets the full width, and each child gets half. This recursive halving is what keeps every subtree centered within its allocated space.

This pattern appears in other tree layout problems as well. Anytime you need to position nodes on a grid where subtrees should not overlap, the power-of-two offset formula is your go-to tool. It works because a complete binary tree of height h has exactly 2^(h+1) - 1 nodes, and the offset formula allocates exactly enough room for each subtree.

Edge cases

Single node: A tree with just a root has height 0. The grid is 1 row and 1 column: [["1"]]. The fill function places the root at [0][0] and returns.

Left-skewed tree: If every node only has a left child, the height is n-1, and the grid becomes very wide (exponential in n). Most cells will be empty strings. The algorithm still works correctly, but be aware the output size grows exponentially with depth.

Right-skewed tree: Same behavior as left-skewed. The grid is wide, and only the rightmost path of columns gets filled. The offset formula handles it without any special cases.

null children: When a node has only one child, the missing side simply does not recurse. The grid cells in that subtree remain as empty strings from initialization.

From understanding to recall

The recall anchor for this problem is: "compute height, allocate grid, recurse with halving offsets." If you remember that the column formula is 2^(height - level - 1), everything else follows mechanically. Height gives you the grid size. The starting column is the midpoint. And the fill function is a standard preorder traversal with two extra parameters.

Practice writing this from scratch a few times. The tricky part is not the recursion itself but getting the offset formula right. Once you can write offset = 1 << (h - r - 1) from memory, the rest is a standard tree DFS. Each attempt should take under five minutes once the pattern clicks.

Related posts

• Maximum Depth of Binary Tree - computing tree height, which is the first step in this problem
• Binary Tree Level Order Traversal - another problem that maps tree structure onto row-based output
• Construct Binary Tree from Preorder and Inorder Traversal - recursive tree construction using offset-based subdivision

The grid placement approach turns a tree into a formatted 2D layout by combining height computation with recursive column offsets. Once you see that each level halves the available space, the formula writes itself. Lock in the pattern, and you will handle any tree-to-grid mapping problem with confidence.