LeetCode 655: Print Binary Tree Solution in Python – A Step-by-Step Guide

Imagine you’re a tree artist tasked with sketching a binary tree—like one with nodes 1, 2, and 3—into a neat grid where each level spreads out evenly, and node values sit precisely where they belong, surrounded by empty spaces. For example, a tree [1, 2, 3] might look like ["", "1", "", "2", "3"] in a grid. That’s the challenge of LeetCode 655: Print Binary Tree, a medium-level problem that’s all about visualizing a binary tree in a structured format. Using Python, we’ll explore two solutions: the Best Solution, a recursive traversal with grid placement for clarity, and an Alternative Solution, a BFS approach with level tracking that’s more iterative but complex. With detailed examples, beginner-friendly breakdowns—especially for the recursive method—and clear code, this guide will help you print that tree, whether you’re new to coding or leveling up. Let’s grab our grid and start sketching!

What Is LeetCode 655: Print Binary Tree?

In LeetCode 655: Print Binary Tree, you’re given the root of a binary tree (nodes with val, left, and right attributes), and your task is to print it in an m x n grid (list of lists of strings) where:

m is the height of the tree.
n = 2^m - 1 (width based on full tree at max height).
Root is at row 0, column (n-1)/2.
Left child of a node at (r, c) is at (r+1, c-2^(h-r-1)).
Right child is at (r+1, c+2^(h-r-1)).
Non-node positions are empty strings ("").

Return the grid. For example, with root = [1, 2, 3, null, 5], you’d build a 3x7 grid showing the tree’s layout. This problem tests your ability to map tree nodes to a 2D structure.

Problem Statement

Input:

root: Root node of a binary tree.

Output: A list of lists of strings—grid representation of the tree.
Rules:

Grid size: m = height, n = 2^m - 1.
Root at (0, (n-1)/2).
Left child: (r+1, c-2^(h-r-1)).
Right child: (r+1, c+2^(h-r-1)).
Empty positions = "".

Constraints

Number of nodes: 1 to 10³.
-100 ≤ Node.val ≤ 100.
Tree height ≤ 10.

Examples

Input: root = [1, 2, 3, null, 5]

Output: [["", "", "", "1", "", "", ""], ["", "2", "", "", "3", "", ""], ["", "", "5", "", "", "", ""]]

Input: root = [1, 2]

Output: [["", "1", ""], ["2", "", ""]]

Input: root = [1]

Output: [["1"]]

These examples set the grid—let’s solve it!

Understanding the Problem: Printing the Tree

To solve LeetCode 655: Print Binary Tree in Python, we need to print a binary tree into an m x n grid, placing each node’s value at a calculated position based on its depth and the tree’s height. A brute-force approach—placing nodes without structure—wouldn’t work; we need a systematic method to compute positions. Since the tree’s layout follows a recursive or level-wise pattern, we can use traversal techniques. We’ll explore:

Best Solution (Recursive Traversal with Grid Placement): O(n) time, O(m * n) space—fast and clear.
Alternative Solution (BFS with Level Tracking): O(n) time, O(w) space—iterative but complex (w = max width).

Let’s start with the recursive solution, breaking it down for beginners.

Best Solution: Recursive Traversal with Grid Placement

Why This Is the Best Solution

The recursive traversal with grid placement is the top choice for LeetCode 655 because it’s efficient—O(n) time with O(m * n) space—and directly maps each node to its grid position using recursion, making it intuitive once you see the pattern. It fits constraints (n ≤ 10³, height ≤ 10) perfectly and avoids complex iteration logic. It’s like painting the tree onto the grid layer by layer!

How It Works

Think of this as a tree painter:

Step 1: Compute Height:

Find tree height h to set grid size: m = h, n = 2^h - 1.

Step 2: Initialize Grid:

Create m x n grid with empty strings.

Step 3: Recursive Placement:

For each node, compute row (depth) and column (based on height and position).
Place node value, recurse on left and right with adjusted columns.

Step 4: Return Grid:

Return filled grid.

It’s like a grid placer—paint and recurse!

Step-by-Step Example

Example: root = [1, 2, 3, null, 5]

Step 1: Height = 3, m = 3, n = 2^3 - 1 = 7.
Step 2: Grid = [[""]7, [""]7, [""]*7].
Step 3: Place nodes:

Root 1: Row 0, Col (7-1)/2 = 3, grid[0][3] = "1".
Left 2: Row 1, Col 3-2^(3-1-1) = 2, grid[1][2] = "2".
Right 3: Row 1, Col 3+2^(3-1-1) = 4, grid[1][4] = "3".
Left of 2 (null): Skip.
Right of 2: 5, Row 2, Col 2-2^(3-2-1) = 2, grid[2][2] = "5".

Step 4: Grid = [["", "", "", "1", "", "", ""], ["", "2", "", "", "3", "", ""], ["", "", "5", "", "", "", ""]].
Output: This grid.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

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: TreeNode) -> List[List[str]]:
        # Step 1: Compute height
        def get_height(node):
            if not node:
                return 0
            return 1 + max(get_height(node.left), get_height(node.right))

        height = get_height(root)
        width = 2 ** height - 1

        # Step 2: Initialize grid
        grid = [[""] * width for _ in range(height)]

        # Step 3: Recursive placement
        def place(node, row, left, right):
            if not node:
                return

            # Compute column for current node
            col = (left + right) // 2
            grid[row][col] = str(node.val)

            # Recurse on children
            place(node.left, row + 1, left, col - 1)
            place(node.right, row + 1, col + 1, right)

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

        # Step 4: Return grid
        return grid

Lines 1-6: TreeNode class (standard).
Lines 10-14: get_height: Compute tree height recursively.
Lines 16-18: Init: Height h, width 2^h - 1, empty grid.
Lines 21-30: place:

Place node at mid-column, recurse on children with adjusted bounds.

Line 32: Start from root.
Time Complexity: O(n)—visit each node once.
Space Complexity: O(m * n)—grid size (m = h, n = 2^h - 1).

This is like a tree printer—place and fill!

Alternative Solution: BFS with Level Tracking

Why an Alternative Approach?

The BFS with level tracking uses breadth-first search—O(n) time, O(w) space (w = max width). It’s more iterative, processing levels and computing positions explicitly, but requires managing node positions manually. It’s like sketching the tree level by level!

How It Works

Picture this as a level sketcher:

Step 1: Compute height for grid size.
Step 2: BFS with position:

Queue nodes with (node, row, col).
Process level-wise, compute child positions.

Step 3: Fill grid with node values.
Step 4: Return grid.

It’s like a level drawer—queue and plot!

Step-by-Step Example

Example: Same as above

Step 1: Height = 3, m = 3, n = 7.
Step 2: BFS:

Queue: [(1, 0, 3)].
Level 0: Pop (1, 0, 3), grid[0][3] = "1", push (2, 1, 2), (3, 1, 4).
Level 1: Pop (2, 1, 2), grid[1][2] = "2", push (5, 2, 2); Pop (3, 1, 4), grid[1][4] = "3".
Level 2: Pop (5, 2, 2), grid[2][2] = "5".

Step 3: Grid = [["", "", "", "1", "", "", ""], ["", "2", "", "", "3", "", ""], ["", "", "5", "", "", "", ""]].
Output: This grid.

Code for BFS Approach

from collections import deque

class Solution:
    def printTree(self, root: TreeNode) -> List[List[str]]:
        # Step 1: Compute height
        def get_height(node):
            if not node:
                return 0
            return 1 + max(get_height(node.left), get_height(node.right))

        height = get_height(root)
        width = 2 ** height - 1

        # Step 2: Initialize grid
        grid = [[""] * width for _ in range(height)]

        # Step 3: BFS with position
        queue = deque([(root, 0, (width - 1) // 2)])
        while queue:
            node, row, col = queue.popleft()
            grid[row][col] = str(node.val)

            if node.left:
                queue.append((node.left, row + 1, col - 2 ** (height - row - 2)))
            if node.right:
                queue.append((node.right, row + 1, col + 2 ** (height - row - 2)))

        # Step 4: Return grid
        return grid

Lines 4-9: Compute height.
Lines 11-13: Init grid.
Lines 16-24: BFS:

Queue with node, row, col; compute child positions, fill grid.

Line 27: Return grid.
Time Complexity: O(n)—visit each node once.
Space Complexity: O(w)—queue size (max width).

It’s a level plotter—queue and place!

Comparing the Two Solutions

Recursive (Best):

Pros: O(n) time, O(m * n) space, clear and recursive.
Cons: Stack space for deep trees.

BFS (Alternative):

Pros: O(n) time, O(w) space, iterative.
Cons: Position calculation complex.

Recursive wins for simplicity.

Additional Examples and Edge Cases

Input: [1]

Output: [["1"]].

Input: [1, 2]

Output: [["", "1", ""], ["2", "", ""]].

Both handle these well.

Complexity Breakdown

Recursive: Time O(n), Space O(m * n).
BFS: Time O(n), Space O(w).

Recursive is optimal for clarity.

Key Takeaways

Recursive: Grid placement—smart!
BFS: Level tracking—clear!
Printing: Trees are fun.
Python Tip: Recursion rocks—see Python Basics.

Final Thoughts: Sketch That Tree

LeetCode 655: Print Binary Tree in Python is a neat visualization challenge. Recursive placement offers clarity and efficiency, while BFS provides an iterative twist. Want more? Try LeetCode 102: Binary Tree Level Order Traversal or LeetCode 104: Maximum Depth of Binary Tree. Ready to draw? Head to Solve LeetCode 655 on LeetCode and print that tree today!