Is Print Binary Tree easy or hard?

Print Binary Tree is considered a medium difficulty problem. The main challenge is calculating the correct column positions using the formula 2^height − 1 and maintaining the correct column ranges while traversing the tree.

Print Binary Tree Python/Java solution

Python and C++ implementations typically use recursive DFS to compute height and place nodes. Java and C# solutions often use a queue with level order traversal. Both strategies rely on the same midpoint column calculation and run in O(n) time.

How to solve Print Binary Tree in O(n)?

First compute the height of the tree. Allocate a matrix with height rows and 2^height − 1 columns. During traversal, place each node at the midpoint of its column range and recursively assign children to the left and right halves. Each node is processed once, giving O(n) time complexity.

What is the best approach for Print Binary Tree?

The recursive DFS placement approach is the most common solution. Compute the tree height, create a matrix of size height x (2^height − 1), and place each node at the midpoint of its valid column range. Recursively assign left and right subtrees to the left and right halves. This runs in O(n) time and uses O(n) space.

Is Print Binary Tree asked at Google/Amazon/Meta?

Tree formatting and traversal problems like Print Binary Tree appear in interviews at companies such as Amazon, Google, and Meta. They test understanding of tree height, recursive traversal, and coordinate-style node placement within structured output.

What data structure is used in Print Binary Tree?

The solution uses a binary tree as input and a 2D string matrix for output. Traversal can be implemented with recursion using depth-first search or with a queue using breadth-first search for level order processing.

What is the time complexity of Print Binary Tree?

The time complexity is O(n) where n is the number of nodes in the tree. Each node is visited once during traversal and placed exactly once in the output matrix. Matrix creation also scales with the number of nodes because the width depends on tree height.

Description Solution Video 12:32

655. Print Binary Tree

Medium67.1% acceptance5 companies

Given the root of a binary tree, construct a 0-indexed m x n string matrix res that represents a formatted layout of the tree. The formatted layout matrix should be constructed using the following rules:

The height of the tree is height and the number of rows m should be equal to height + 1.
The number of columns n should be equal to 2^height+1 - 1.
Place the root node in the middle of the top row (more formally, at location res[0][(n-1)/2]).
For each node that has been placed in the matrix at position res[r][c], place its left child at res[r+1][c-2^height-r-1] and its right child at res[r+1][c+2^height-r-1].
Continue this process until all the nodes in the tree have been placed.
Any empty cells should contain the empty string "".

Return the constructed matrix res.

Example 1:

Input: root = [1,2]
Output: 
[["","1",""],
 ["2","",""]]

Example 2:

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

Constraints:

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

Asked at 5 companies

Poynt

Google Amazon Microsoft Meta

Topics

12:32

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,2]

Input

[1,2,3,null,4]

Your code is saved on this device.Solution