# 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:

| Rule | Meaning |
|---|---|
| Rows | One row for each tree level |
| Columns | Enough columns to center every subtree |
| Root placement | The root goes in the middle of the first row |
| Child placement | Children are placed one row below their parent |
| Empty cells | Empty positions contain `""` |

If the tree height is `height`, then:

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

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | The root of a binary tree |
| Output | A 2D list of strings |
| Empty cell | `""` |
| Node cell | The node value converted to a string |
| Matrix rows | `height + 1` |
| Matrix columns | `2^(height + 1) - 1` |

Example function shape:

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

## Examples

Consider this tree:

```text
  1
 /
2
```

The height is `1`.

So the matrix has:

```text
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:

```python
[
    ["", "1", ""],
    ["2", "", ""],
]
```

Another example:

```text
    1
   / \
  2   3
   \
    4
```

The height is `2`.

So the matrix has:

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

Output:

```python
[
    ["", "", "", "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:

```text
res[row][col]
```

then its children are placed using an offset.

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

```text
2^(height - row - 1)
```

So:

```text
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:

| Tree | Height |
|---|---|
| Empty tree | `-1` |
| Single node | `0` |
| Root with one child | `1` |

The recursive formula is:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n + height * 2^height)` | We visit nodes and initialize the output matrix |
| Space | `O(height * 2^height)` | The result matrix has that many cells |

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

The recursion stack uses `O(height)` extra space.

## Implementation

```python
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:

```python
if node is None:
    return -1
```

This makes a leaf node height `0`, because:

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

After computing the height, we calculate the matrix size:

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

The expression:

```python
1 << (height + 1)
```

means:

```text
2^(height + 1)
```

Then we create the result matrix:

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

The placement function receives a node and its matrix position:

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

It writes the node value as a string:

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

Then it computes the child offset:

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

The left child moves left by that offset:

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

The right child moves right by that offset:

```python
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

```python
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:

| Test | Why |
|---|---|
| Root with left child | Checks basic centering and left placement |
| Tree of height `2` | Checks recursive offsets |
| Single node | Checks smallest matrix |
| Negative value | Confirms node values are converted to strings |