LeetCode 655: Print Binary Tree

Problem Restatement

We are given the root of a binary tree.

We need to return a 2D string matrix that represents the tree in a formatted layout.

The layout follows fixed rules:

If the tree height is height, then:

rows = height + 1
cols = 2^(height + 1) - 1

Here, height is measured in edges. A single-node tree has height 0.

Input and Output

Example function shape:

def printTree(root: Optional[TreeNode]) -> List[List[str]]:
    ...

Examples

Consider this tree:

  1
 /
2

The height is 1.

So the matrix has:

rows = 2
cols = 2^(1 + 1) - 1 = 3

The root 1 goes in the middle of row 0.

The left child 2 goes below and to the left.

Output:

[
    ["", "1", ""],
    ["2", "", ""],
]

Another example:

    1
   / \
  2   3
   \
    4

The height is 2.

So the matrix has:

rows = 3
cols = 2^(2 + 1) - 1 = 7

Output:

[
    ["", "", "", "1", "", "", ""],
    ["", "2", "", "", "", "3", ""],
    ["", "", "4", "", "", "", ""],
]

First Thought: Build the Matrix Level by Level

A binary tree naturally has levels, so we might think about using BFS.

BFS can visit the nodes level by level, but the hard part is not visiting nodes. The hard part is placing each node in the correct column.

The column of a child depends on:

1. The column of its parent.
2. The current row.
3. The total height of the tree.

So before placing nodes, we first need to know the tree height.

Key Insight

The matrix width is based on the height of the tree.

Once we know the height, every node placement becomes deterministic.

If a node is placed at:

res[row][col]

then its children are placed using an offset.

For a node at row row, the offset for its children is:

2^(height - row - 1)

So:

left child column  = col - offset
right child column = col + offset

This keeps subtrees centered under their parents.

Algorithm

Use two DFS passes.

First DFS computes the height of the tree.

Second DFS places nodes into the matrix.

The steps are:

1. Compute the height of the tree.
2. Create a matrix filled with empty strings.
3. Put the root at the middle column.
4. Recursively place left and right children using the offset formula.
5. Return the matrix.

Height Computation

We define height as the number of edges on the longest path from the root to a leaf.

So:

The recursive formula is:

height(node) = 1 + max(height(node.left), height(node.right))

For None, return -1.

This makes a leaf node have height 0.

Correctness

The height function computes the longest root-to-leaf edge count. Therefore, the algorithm creates exactly height + 1 rows, one for each tree level.

The number of columns is 2^(height + 1) - 1, which gives enough space to place the root in the center and recursively reserve symmetric space for both subtrees.

The placement DFS starts by placing the root at the middle of the first row. This matches the required rule.

For every node placed at row r and column c, the algorithm places its left child at c - 2^(height-r-1) and its right child at c + 2^(height-r-1). These are exactly the required child positions.

The DFS visits every node once and places each node value into its required cell. All other cells remain as empty strings because the matrix was initialized with "".

Therefore, the returned matrix is exactly the formatted layout required by the problem.

Complexity

Since the matrix itself must be returned, the output size dominates the space cost.

The recursion stack uses O(height) extra space.

Implementation

from typing import List, Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
        def get_height(node: Optional[TreeNode]) -> int:
            if node is None:
                return -1

            return 1 + max(
                get_height(node.left),
                get_height(node.right),
            )

        height = get_height(root)
        rows = height + 1
        cols = (1 << (height + 1)) - 1

        result = [[""] * cols for _ in range(rows)]

        def place(node: Optional[TreeNode], row: int, col: int) -> None:
            if node is None:
                return

            result[row][col] = str(node.val)

            offset = 1 << (height - row - 1)

            if node.left is not None:
                place(node.left, row + 1, col - offset)

            if node.right is not None:
                place(node.right, row + 1, col + offset)

        place(root, 0, cols // 2)

        return result

Code Explanation

The height helper handles empty children with:

if node is None:
    return -1

This makes a leaf node height 0, because:

1 + max(-1, -1) = 0

After computing the height, we calculate the matrix size:

rows = height + 1
cols = (1 << (height + 1)) - 1

The expression:

1 << (height + 1)

means:

2^(height + 1)

Then we create the result matrix:

result = [[""] * cols for _ in range(rows)]

The placement function receives a node and its matrix position:

def place(node: Optional[TreeNode], row: int, col: int) -> None:

It writes the node value as a string:

result[row][col] = str(node.val)

Then it computes the child offset:

offset = 1 << (height - row - 1)

The left child moves left by that offset:

place(node.left, row + 1, col - offset)

The right child moves right by that offset:

place(node.right, row + 1, col + offset)

We only call place on existing children, so the offset is never needed below the last row.

Testing

def run_tests():
    s = Solution()

    # Tree:
    #   1
    #  /
    # 2
    root = TreeNode(1, TreeNode(2), None)

    assert s.printTree(root) == [
        ["", "1", ""],
        ["2", "", ""],
    ]

    # Tree:
    #     1
    #    / \
    #   2   3
    #    \
    #     4
    root = TreeNode(
        1,
        TreeNode(2, None, TreeNode(4)),
        TreeNode(3),
    )

    assert s.printTree(root) == [
        ["", "", "", "1", "", "", ""],
        ["", "2", "", "", "", "3", ""],
        ["", "", "4", "", "", "", ""],
    ]

    # Single node.
    root = TreeNode(7)

    assert s.printTree(root) == [
        ["7"],
    ]

    # Tree with negative value.
    root = TreeNode(-1, None, TreeNode(2))

    assert s.printTree(root) == [
        ["", "-1", ""],
        ["", "", "2"],
    ]

    print("all tests passed")

run_tests()

Test meaning: