LeetCode 655 - Print Binary Tree

The problem asks us to transform a binary tree into a formatted 2D string matrix representation. Each node must appear in a specific row and column based on its position in the tree. The output is not simply a traversal order, it is a visual layout of the tree structure.

leetcodemediumtreedepth-first-searchbreadth-first-searchbinary-tree

LeetCode Problem 655

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to transform a binary tree into a formatted 2D string matrix representation. Each node must appear in a specific row and column based on its position in the tree. The output is not simply a traversal order, it is a visual layout of the tree structure.

We are given the root of a binary tree. From this tree, we must construct a matrix res where:

  • The number of rows depends on the height of the tree.
  • The number of columns depends exponentially on the height.
  • Each node value is placed in a carefully calculated column so that the tree appears centered and symmetric.

The height of a tree is defined as the number of edges on the longest path from the root to a leaf. However, in this problem, the matrix row count is height + 1, which effectively corresponds to the number of levels in the tree.

The width formula is:

$$n = 2^{height+1} - 1$$

This width guarantees enough horizontal spacing for every subtree.

The placement rules are the most important part of the problem:

  • The root goes in the center column of the first row.
  • Every left child is placed halfway to the left boundary of its subtree.
  • Every right child is placed halfway to the right boundary of its subtree.

This recursive spacing creates a visually balanced tree representation.

The constraints are relatively small:

  • At most 210 nodes
  • Maximum depth is 10

These limits tell us that efficiency is not extremely critical, but correctness of positioning is essential. Since the maximum depth is small, even matrix sizes remain manageable:

$$2^{11} - 1 = 2047$$

So the largest possible width is only 2047 columns.

Several edge cases are important:

  • A tree with only one node
  • A completely skewed tree, where every node only has a left or right child
  • Sparse trees with missing children
  • Negative node values
  • Trees where subtrees have very different heights

A naive implementation may miscalculate spacing or place nodes outside matrix bounds if the recursive offsets are not handled carefully.

Approaches

Brute Force Approach

A brute force approach would attempt to explicitly simulate the layout by repeatedly calculating subtree widths for every node placement.

For each node, we could:

  1. Compute the width required for its left subtree.
  2. Compute the width required for its right subtree.
  3. Determine the node's column position from those widths.
  4. Recursively repeat the process.

This works because the placement of each node depends on the available horizontal space beneath it.

However, this approach becomes inefficient because subtree dimensions are recomputed many times. If every recursive call recalculates heights or widths for descendants, the same work is repeated repeatedly across the tree.

Although the input size is small enough that this would still pass, it is unnecessarily expensive and harder to reason about.

Optimal Approach

The key insight is that the matrix dimensions are completely determined by the tree height.

Once we know the height:

  • Total rows are fixed.
  • Total columns are fixed.
  • Every node position can be computed directly using recursive midpoint ranges.

Instead of recalculating subtree widths repeatedly, we recursively assign nodes into intervals:

  • Each node owns a column range [left, right].
  • The node itself is placed at the midpoint.
  • The left child receives the left half of the interval.
  • The right child receives the right half.

This works naturally because binary tree layouts are recursively symmetric.

The recursive interval strategy is elegant because:

  • Every subtree automatically receives exactly the correct amount of space.
  • No recomputation of widths is needed.
  • The placement logic becomes simple midpoint arithmetic.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(h) Recomputes subtree dimensions repeatedly
Optimal O(n + 2^h) O(2^h × h) Computes height once and places nodes directly

Algorithm Walkthrough

Step 1: Compute the tree height

We first compute the height of the tree using DFS recursion.

For every node:

  • Height of an empty node is -1
  • Height of a leaf node is 0
  • Otherwise:

$$1 + \max(leftHeight, rightHeight)$$

We need the height because it determines both matrix dimensions and node spacing.

Step 2: Compute matrix dimensions

Once the height is known:

  • Number of rows:

$$rows = height + 1$$

  • Number of columns:

$$cols = 2^{height+1} - 1$$

We then initialize the matrix with empty strings.

Step 3: Start recursive placement

We recursively place nodes into the matrix.

Each recursive call receives:

  • Current node
  • Current row
  • Left column boundary
  • Right column boundary

The node belongs in the midpoint:

$$mid = (left + right) // 2$$

We place the node value at:

matrix[row][mid]

Step 4: Recurse into left subtree

The left child receives the left half of the current interval:

[left, mid - 1]

This guarantees the subtree remains centered within its allocated space.

Step 5: Recurse into right subtree

The right child receives the right half:

[mid + 1, right]

Again, this preserves symmetry.

Step 6: Continue until all nodes are placed

The recursion stops when:

  • The node is None
  • The interval becomes invalid

At the end, every node occupies its correct matrix position.

Why it works

The algorithm maintains an important invariant:

Every subtree is assigned a column interval large enough to contain the entire subtree symmetrically.

Because each node is always placed at the midpoint of its interval, its left and right subtrees naturally receive equal spacing on either side. Since the recursion mirrors the tree structure exactly, all nodes are placed in the correct relative positions.

Python Solution

# 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

from typing import List, Optional

class Solution:
    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
        
        def get_height(node: Optional[TreeNode]) -> int:
            if not node:
                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 = [["" for _ in range(cols)] for _ in range(rows)]
        
        def place(
            node: Optional[TreeNode],
            row: int,
            left: int,
            right: int
        ) -> None:
            
            if not node or left > right:
                return
            
            mid = (left + right) // 2
            
            result[row][mid] = str(node.val)
            
            place(node.left, row + 1, left, mid - 1)
            place(node.right, row + 1, mid + 1, right)
        
        place(root, 0, 0, cols - 1)
        
        return result

The implementation starts by computing the tree height using a recursive DFS helper. Returning -1 for None simplifies the height formula because a leaf node then naturally becomes height 0.

After computing the height, the matrix dimensions are derived directly from the formulas given in the problem statement.

The matrix is initialized entirely with empty strings because every unused cell must contain "".

The recursive place function performs the actual layout logic. Each call receives the current subtree's valid column range. The midpoint of this range becomes the node's position. Then the interval is split into two smaller intervals for the left and right subtrees.

This recursive interval subdivision exactly matches the required formatting rules.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func printTree(root *TreeNode) [][]string {

    var getHeight func(node *TreeNode) int

    getHeight = func(node *TreeNode) int {
        if node == nil {
            return -1
        }

        leftHeight := getHeight(node.Left)
        rightHeight := getHeight(node.Right)

        if leftHeight > rightHeight {
            return leftHeight + 1
        }

        return rightHeight + 1
    }

    height := getHeight(root)

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

    result := make([][]string, rows)

    for i := 0; i < rows; i++ {
        result[i] = make([]string, cols)
    }

    var place func(
        node *TreeNode,
        row int,
        left int,
        right int,
    )

    place = func(
        node *TreeNode,
        row int,
        left int,
        right int,
    ) {
        if node == nil || left > right {
            return
        }

        mid := (left + right) / 2

        result[row][mid] = strconv.Itoa(node.Val)

        place(node.Left, row+1, left, mid-1)
        place(node.Right, row+1, mid+1, right)
    }

    place(root, 0, 0, cols-1)

    return result
}

The Go implementation follows the same recursive interval strategy as the Python version.

One important Go-specific detail is that slices are automatically initialized with empty strings, so we do not need to manually fill the matrix.

Another difference is integer-to-string conversion. Go requires strconv.Itoa() to convert node values before storing them in the matrix.

The recursion structure and midpoint calculations remain identical.

Worked Examples

Example 1

Input:

    1
   /
  2

Tree height:

height = 1

Matrix dimensions:

rows = 2
cols = 3

Initial matrix:

Row Contents
0 ["", "", ""]
1 ["", "", ""]

Placement Steps

Node Row Interval Mid Matrix Update
1 0 [0, 2] 1 result[0][1] = "1"
2 1 [0, 0] 0 result[1][0] = "2"

Final matrix:

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

Example 2

Input:

        1
       / \
      2   3
       \
        4

Tree height:

height = 2

Matrix dimensions:

rows = 3
cols = 7

Initial matrix:

Row Contents
0 ["","","","","","",""]
1 ["","","","","","",""]
2 ["","","","","","",""]

Placement Steps

Node Row Interval Mid Placement
1 0 [0, 6] 3 result[0][3] = "1"
2 1 [0, 2] 1 result[1][1] = "2"
3 1 [4, 6] 5 result[1][5] = "3"
4 2 [2, 2] 2 result[2][2] = "4"

Final matrix:

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

Complexity Analysis

Measure Complexity Explanation
Time O(n + 2^h) DFS visits each node once, matrix initialization dominates width
Space O(2^h × h) Matrix storage plus recursion stack

The DFS height computation takes O(n) time. The placement DFS also visits every node exactly once, contributing another O(n).

However, initializing the matrix requires allocating:

$$(height + 1) \times (2^{height+1} - 1)$$

cells, which dominates the runtime for large heights.

The space complexity is similarly dominated by the output matrix itself. The recursion stack adds at most O(h) extra space.

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

solution = Solution()

# Example 1
root = TreeNode(1, TreeNode(2))
assert solution.printTree(root) == [
    ["", "1", ""],
    ["2", "", ""]
]  # simple left child

# Example 2
root = TreeNode(
    1,
    TreeNode(2, None, TreeNode(4)),
    TreeNode(3)
)

assert solution.printTree(root) == [
    ["", "", "", "1", "", "", ""],
    ["", "2", "", "", "", "3", ""],
    ["", "", "4", "", "", "", ""]
]  # sparse subtree structure

# Single node tree
root = TreeNode(1)

assert solution.printTree(root) == [
    ["1"]
]  # minimum possible tree

# Completely right skewed tree
root = TreeNode(
    1,
    None,
    TreeNode(
        2,
        None,
        TreeNode(3)
    )
)

assert solution.printTree(root) == [
    ["", "", "", "1", "", "", ""],
    ["", "", "", "", "", "2", ""],
    ["", "", "", "", "", "", "3"]
]  # right-heavy structure

# Completely left skewed tree
root = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(3)
    )
)

assert solution.printTree(root) == [
    ["", "", "", "1", "", "", ""],
    ["", "2", "", "", "", "", ""],
    ["3", "", "", "", "", "", ""]
]  # left-heavy structure

# Negative values
root = TreeNode(
    -1,
    TreeNode(-2),
    TreeNode(-3)
)

assert solution.printTree(root) == [
    ["", "-1", ""],
    ["-2", "", "-3"]
]  # negative node values

# Full binary tree
root = TreeNode(
    1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3, TreeNode(6), TreeNode(7))
)

assert solution.printTree(root) == [
    ["", "", "", "1", "", "", ""],
    ["", "2", "", "", "", "3", ""],
    ["4", "", "5", "", "6", "", "7"]
]  # perfectly balanced tree

Test Summary

Test Why
Example 1 Validates basic left-child placement
Example 2 Validates sparse subtree handling
Single node tree Tests minimum input size
Right skewed tree Tests extreme right recursion
Left skewed tree Tests extreme left recursion
Negative values Ensures string conversion works correctly
Full binary tree Validates symmetric placement

Edge Cases

A single-node tree is the smallest possible input and can easily expose off-by-one mistakes in height or width calculations. If height is computed incorrectly, the algorithm may allocate zero columns or place the node outside the matrix. This implementation handles it correctly because a leaf node has height 0, producing a 1 × 1 matrix.

A completely skewed tree is another important edge case. In a left-skewed or right-skewed tree, recursive intervals become very narrow on one side while remaining empty on the other. Incorrect midpoint calculations can cause overlapping placements or invalid indices. The recursive interval subdivision guarantees that every node still receives a valid position.

Sparse trees with missing children are particularly error-prone because recursive placement must skip None nodes without disrupting subtree alignment. This implementation handles missing children naturally by immediately returning when the node is None, while still preserving the correct intervals for existing descendants.

Negative node values also deserve attention because the output matrix stores strings, not integers. Forgetting conversion would produce type errors. Both implementations explicitly convert node values to strings before insertion into the matrix.