Print Binary Tree solution and explanation
Google
7 more videos on this problem
花花酱 LeetCode 655. Print Binary Tree - 刷题找工作 EP9Hua Hua · 12:32 · 5K views
Print Binary Tree (to Matrix) (Medium) | Tree | Top 52 Uber LeetCode Premium Coding QuestionsAakash Verma · 11:57 · 898 views
LeetCode 655 Print Binary Tree #leetcode #depthfirstsearchAI Learning Corner · 5:43 · 821 views
Learning wiz Rita Leetcode 655 Print Binary Tree PythonRita zeng · 14:14 · 745 views
Print Binary Tree | Leetcode 655 | Approach + Code with explanation.Pirai's Academy · 11:33 · 269 views
LeetCode - 655. Print Binary Tree | DFS | JavaOrkhan Gasanov · 4:05 · 136 views
No Sound Leetcode 655: Print Binary TreeExtremeProgrammer · 4:11 · 54 views
LeetCode 655: Print Binary TreeAlitaCode · 30:08 · 34 views
The problem
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
heightand the number of rowsmshould be equal toheight + 1. - The number of columns
nshould be equal to2height+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 atres[r+1][c-2height-r-1]and its right child atres[r+1][c+2height-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, 210]. -99 <= Node.val <= 99- The depth of the tree will be in the range
[1, 10].
Approach overview
Problem Overview: Given the root of a binary tree, return a 2D string matrix that visually represents the tree structure. The matrix width must be 2^height - 1, and each node is placed at the midpoint of its valid column range so that left and right children appear symmetrically below the parent.
Approach 1: Recursive Placement of Nodes (DFS) (Time: O(n), Space: O(n))
This approach uses Depth-First Search to place nodes directly in the correct matrix positions. First compute the tree height using a recursive traversal. The matrix dimensions become height x (2^height - 1). During DFS, each node is assigned a column based on the midpoint of its current column range [left, right]. Place the node value at that midpoint, then recursively process the left child with range [left, mid-1] and the right child with [mid+1, right]. This works because every subtree occupies exactly half of its parent’s horizontal space. The recursion naturally mirrors the structure of a Binary Tree, making the placement logic clean and predictable. This is the most common and readable solution.
Approach 2: Iterative Level Order Traversal (BFS) (Time: O(n), Space: O(n))
This version uses Breadth-First Search with a queue to process nodes level by level. After computing the tree height and initializing the matrix, push the root into a queue along with its column boundaries. Each queue entry stores (node, row, leftBound, rightBound). When processing a node, compute the midpoint column and write its value into the matrix. Then push the left and right children into the queue with updated column ranges. BFS makes the row index explicit and avoids recursion depth limits. The placement logic is the same midpoint calculation used in the DFS solution, but controlled iteratively.
Recommended for interviews: The recursive DFS placement is usually the expected solution because it maps directly to the tree structure and requires less bookkeeping. Interviewers like it because the midpoint calculation clearly shows you understand how the visual layout relates to tree height. The BFS approach is equally optimal in complexity and demonstrates familiarity with queue-based traversal, but the DFS version is typically shorter and easier to reason about.
Approach 1: Recursive Placement of Nodes
This approach involves calculating the height of the binary tree first. Once we have the height, we can determine the size of the resulting matrix with m = height + 1 and n = 2height + 1 - 1. We then recursively place each node starting from the root at res[0][(n-1)/2]. For any node at position res[r][c], its left child is placed at res[r+1][c-2height-r-1] and its right child at res[r+1][c+2height-r-1].
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]]:
def getHeight(node):
if not node:
return -1
return 1 + max(getHeight(node.left), getHeight(node.right))
height = getHeight(root)
m, n = height + 1, (1 << (height + 1)) - 1
res = [['' for _ in range(n)] for _ in range(m)]
def fill(res, node, r, c, height):
if not node:
return
res[r][c] = str(node.val)
if node.left:
fill(res, node.left, r + 1, c - (1 << (height - r - 1)), height)
if node.right:
fill(res, node.right, r + 1, c + (1 << (height - r - 1)), height)
fill(res, root, 0, (n - 1) // 2, height)
return res#include <vector>
#include <string>
#include <cmath>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
class Solution {
public:
int getHeight(TreeNode* root) {
if (!root) return -1;
return 1 + max(getHeight(root->left), getHeight(root->right));
}
void fill(TreeNode* node, vector<vector<string>> &res, int r, int c, int height) {
if (!node) return;
res[r][c] = to_string(node->val);
if (node->left)
fill(node->left, res, r + 1, c - (1 << (height - r - 1)), height);
if (node->right)
fill(node->right, res, r + 1, c + (1 << (height - r - 1)), height);
}
vector<vector<string>> printTree(TreeNode* root) {
int height = getHeight(root);
int m = height + 1;
int n = (1 << (height + 1)) - 1;
vector<vector<string>> res(m, vector<string>(n, ""));
fill(root, res, 0, (n - 1) / 2, height);
return res;
}
};First, we calculate the height of the tree to determine the dimensions of the result matrix. Then, using recursion, we place each node at its appropriate position. The recursive function fill places the root at the center and calculates positions for child nodes using a power of two shifts according to their level in the tree.
Time Complexity: O(m * n), where m and n are the dimensions of the matrix. The recursive function visits each node once.
Space Complexity: O(m * n) for the result matrix.
Approach 2: Iterative Level Order Traversal
This approach uses an iterative method, leveraging a queue for level order traversal to place nodes in the matrix. We still need to calculate the height first to know the matrix size. Using a queue, nodes are enqueued with their respective positions, and at each level, node positions are calculated based on their level and placed in the matrix iteratively.
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List<List<String>> printTree(TreeNode root) {
int height = getHeight(root);
int m = height + 1, n = (1 << (height + 1)) - 1;
String[][] res = new String[m][n];
for (String[] row: res)
Arrays.fill(row, "");
Queue<Object[]> queue = new LinkedList<>();
queue.add(new Object[]{root, 0, (n - 1) / 2});
while (!queue.isEmpty()) {
Object[] tuple = queue.poll();
TreeNode node = (TreeNode) tuple[0];
int r = (int) tuple[1], c = (int) tuple[2];
res[r][c] = Integer.toString(node.val);
int offset = 1 << (height - r - 1);
if (node.left != null)
queue.add(new Object[]{node.left, r + 1, c - offset});
if (node.right != null)
queue.add(new Object[]{node.right, r + 1, c + offset});
}
List<List<String>> ans = new ArrayList<>();
for (String[] row: res)
ans.add(Arrays.asList(row));
return ans;
}
private int getHeight(TreeNode node) {
if (node == null) return -1;
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<IList<string>> PrintTree(TreeNode root) {
int height = GetHeight(root);
int m = height + 1, n = (1 << (height + 1)) - 1;
string[][] res = new string[m][];
for (int i = 0; i < m; i++)
res[i] = new string[n];
var queue = new Queue<(TreeNode node, int r, int c)>();
queue.Enqueue((root, 0, (n - 1) / 2));
while (queue.Count > 0) {
var (node, r, c) = queue.Dequeue();
res[r][c] = node.val.ToString();
int offset = 1 << (height - r - 1);
if (node.left != null)
queue.Enqueue((node.left, r + 1, c - offset));
if (node.right != null)
queue.Enqueue((node.right, r + 1, c + offset));
}
var result = new List<IList<string>>();
foreach (var row in res)
result.Add(new List<string>(row));
return result;
}
private int GetHeight(TreeNode node) {
if (node == null) return -1;
return 1 + Math.Max(GetHeight(node.left), GetHeight(node.right));
}
}This solution utilizes an iterative approach with a queue for BFS-like level order traversal. In this method, all nodes are processed level by level, and their positions are calculated without recursion by using a queue to manage each node and its column index.
Time Complexity: O(m * n), as we traverse the tree and fill the matrix.
Space Complexity: O(m * n) for storing the output matrix.
Approach 3: Default Approach
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function printTree(root: TreeNode | null): string[][] {
const getHeight = (root: TreeNode | null, h: number) => {
if (root == null) {
return h - 1;
}
return Math.max(getHeight(root.left, h + 1), getHeight(root.right, h + 1));
};
const height = getHeight(root, 0);
const m = height + 1;
const n = 2 ** (height + 1) - 1;
const res: string[][] = Array.from({ length: m }, () => new Array(n).fill(''));
const dfs = (root: TreeNode | null, i: number, j: number) => {
if (root === null) {
return;
}
const { val, left, right } = root;
res[i][j] = val + '';
dfs(left, i + 1, j - 2 ** (height - i - 1));
dfs(right, i + 1, j + 2 ** (height - i - 1));
};
dfs(root, 0, (n - 1) >>> 1);
return res;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func printTree(root *TreeNode) [][]string {
var height func(root *TreeNode) int
height = func(root *TreeNode) int {
if root == nil {
return -1
}
return 1 + max(height(root.Left), height(root.Right))
}
h := height(root)
m, n := h+1, (1<<(h+1))-1
ans := make([][]string, m)
for i := range ans {
ans[i] = make([]string, n)
for j := range ans[i] {
ans[i][j] = ""
}
}
var dfs func(root *TreeNode, r, c int)
dfs = func(root *TreeNode, r, c int) {
if root == nil {
return
}
ans[r][c] = strconv.Itoa(root.Val)
dfs(root.Left, r+1, c-int(math.Pow(float64(2), float64(h-r-1))))
dfs(root.Right, r+1, c+int(math.Pow(float64(2), float64(h-r-1))))
}
dfs(root, 0, (n-1)/2)
return ans
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
fn get_height(root: &Option<Rc<RefCell<TreeNode>>>, h: u32) -> u32 {
if let Some(node) = root {
let node = node.borrow();
return Self::get_height(&node.left, h + 1).max(Self::get_height(&node.right, h + 1));
}
h - 1
}
fn dfs(
root: &Option<Rc<RefCell<TreeNode>>>,
i: usize,
j: usize,
res: &mut Vec<Vec<String>>,
height: u32,
) {
if root.is_none() {
return;
}
let node = root.as_ref().unwrap().borrow();
res[i][j] = node.val.to_string();
Self::dfs(
&node.left,
i + 1,
j - (2usize).pow(height - (i as u32) - 1),
res,
height,
);
Self::dfs(
&node.right,
i + 1,
j + (2usize).pow(height - (i as u32) - 1),
res,
height,
);
}
pub fn print_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<String>> {
let height = Self::get_height(&root, 0);
let m = (height + 1) as usize;
let n = (2usize).pow(height + 1) - 1;
let mut res = vec![vec![String::new(); n]; m];
Self::dfs(&root, 0, (n - 1) >> 1, &mut res, height);
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Placement of Nodes | Time Complexity: |
| Iterative Level Order Traversal | Time Complexity: |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Placement of Nodes (DFS) | O(n) | O(n) | Best general solution. Clean recursion that mirrors the tree structure. |
| Iterative Level Order Traversal (BFS) | O(n) | O(n) | Useful when avoiding recursion or when explicitly processing nodes by level. |
Frequently asked questions
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.