#655

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Print Binary Tree

Print Binary Tree requires arranging a binary tree into a visually structured matrix using precise traversal and positioning rules.

tree depth first search breadth first search binary tree

Problem Statement

Given the root of a binary tree, construct a 0-indexed m x n string matrix that represents the tree visually. Each node's value should occupy a single cell, and empty cells are filled with empty strings. The matrix must maintain tree symmetry so that the parent is centered above its children, and the width is sufficient to accommodate all nodes without overlap.

Return the fully constructed matrix. For example, given root = [1,2], the output should be [["","1",""],["2","",""]]. Constraints include tree node values between -99 and 99, total nodes from 1 to 210, and tree depth from 1 to 10.

Examples

Example 1

Input: root = [1,2]

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

Example details omitted.

Example 2

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

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

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 210].
-99 <= Node.val <= 99
The depth of the tree will be in the range [1, 10].

Solution Approach

Determine Tree Depth and Matrix Dimensions

Compute the maximum depth of the binary tree to establish the number of rows. Calculate the number of columns as 2^depth - 1 to guarantee enough space for symmetric placement. This step prevents overlap when filling child nodes during traversal.

Recursive DFS with Position Tracking

Use a depth-first search to traverse the tree, passing current row, column range, and mid-point for placement. Insert each node's value at the computed middle column for its row. Recursively apply this for left and right subtrees with updated column ranges, ensuring symmetry.

Fill Matrix and Return Result

Initialize the matrix with empty strings. During DFS, populate the matrix with node values at calculated positions. After traversal, return the matrix. Edge cases like missing children automatically leave empty strings, maintaining proper tree formatting.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for traversing all n nodes of the tree. Space complexity is O(n) for storing the resulting matrix and O(h) for the recursion stack, where h is the tree height.

What Interviewers Usually Probe

They may emphasize correct node placement for symmetric visualization.
Expect discussion of DFS versus BFS for position calculation.
Watch for questions about handling null children and empty cells.

Common Pitfalls or Variants

Common pitfalls

Miscalculating column mid-points causing misaligned nodes.
Not initializing the matrix to correct dimensions before filling values.
Confusing depth and height, leading to incorrect row or column counts.

Follow-up variants

Output tree nodes level by level but preserve relative horizontal spacing for symmetry.
Print only the left or right subtree matrix while maintaining column alignment.
Adapt to non-binary trees, adjusting column calculation for multiple children per node.

FAQ

What is the main challenge in Print Binary Tree?

The challenge lies in calculating correct positions for each node to maintain tree symmetry in the output matrix.

Can BFS be used instead of DFS for this problem?

Yes, BFS can work, but it requires tracking column ranges for each level to ensure proper placement, which is less intuitive than DFS.

How do I handle null nodes in the matrix?

Null nodes are left as empty strings in the matrix, preserving spacing and symmetry for parent nodes.

What are common mistakes when implementing this solution?

Common mistakes include misaligning nodes, using incorrect column ranges, or not initializing the matrix to the correct size.

Does the solution work for trees of depth 10?

Yes, as long as the matrix is initialized to 2^depth - 1 columns, the algorithm handles maximum depth without overlap.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

# 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 height(root):
            if root is None:
                return -1
            return 1 + max(height(root.left), height(root.right))

        def dfs(root, r, c):
            if root is None:
                return
            ans[r][c] = str(root.val)
            dfs(root.left, r + 1, c - 2 ** (h - r - 1))
            dfs(root.right, r + 1, c + 2 ** (h - r - 1))

        h = height(root)
        m, n = h + 1, 2 ** (h + 1) - 1
        ans = [[""] * n for _ in range(m)]
        dfs(root, 0, (n - 1) // 2)
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

# 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 height(root):
            if root is None:
                return -1
            return 1 + max(height(root.left), height(root.right))

        def dfs(root, r, c):
            if root is None:
                return
            ans[r][c] = str(root.val)
            dfs(root.left, r + 1, c - 2 ** (h - r - 1))
            dfs(root.right, r + 1, c + 2 ** (h - r - 1))

        h = height(root)
        m, n = h + 1, 2 ** (h + 1) - 1
        ans = [[""] * n for _ in range(m)]
        dfs(root, 0, (n - 1) // 2)
        return ans

Continue Practicing

#653 two sum iv input is a bst #662 maximum width of binary tree #637 average of levels in binary tree