# Print Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/print-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/print-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
---
## 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 `height` and the number of rows `m` should be equal to `height + 1`.
* The number of columns `n` should be equal to `2height+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-2height-r-1]` and its **right child** at `res[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:**

![](https://assets.glich.co/dsa/print-binary-tree/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/print-binary-tree/image1.jpg) 

**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]`.

# Approaches
## Two-Pass Breadth-First Search (BFS)
This approach uses a two-pass strategy based on Breadth-First Search (BFS). The first pass is to determine the height of the binary tree, which is necessary to calculate the dimensions of the output matrix. The second pass fills this matrix by performing another BFS traversal. A queue is used to keep track of nodes and their specific row and column indices for placement in the matrix.
**Time:** O(H * 2^H), where H is the height of the tree. The height calculation takes O(N) time (N is the number of nodes). The matrix initialization takes O(rows * cols) = O((H+1) * (2^(H+1)-1)) = O(H * 2^H). The filling pass takes O(N). The dominant factor is the matrix initialization. · **Space:** O(H * 2^H), where H is the height of the tree. This is dominated by the space required for the output matrix. The auxiliary space for the BFS queue is O(W), where W is the maximum width of the tree.
**Pros:** The iterative nature of BFS avoids recursion, which can prevent stack overflow errors on extremely deep trees (though not an issue with this problem's constraints).; The logic follows a level-by-level construction, which can be intuitive to reason about.
**Cons:** The auxiliary space required for the BFS queue can be large for wide, bushy trees. In the worst case of a complete binary tree, the width `W` can be proportional to the number of nodes `N`, leading to `O(N)` auxiliary space.
### Explanation
The core idea is to first find the geometry of the final matrix and then populate it. The geometry (number of rows and columns) depends entirely on the tree's height.

**1. Height Calculation (BFS):**
A level-order traversal is a natural fit for finding the height. We traverse the tree level by level, incrementing a counter for each level. The final count (starting from 0) gives the height.

**2. Matrix Initialization:**
Once the height `H` is known, the matrix dimensions are `m = H + 1` and `n = 2^(H+1) - 1`. We create an `m x n` list of lists (or 2D array) and pre-fill it with empty strings `""`.

**3. Filling the Matrix (BFS):**
We use a queue to manage the nodes to be placed. To handle the positioning, the queue stores a state object containing the `TreeNode`, its `row`, and its `col`. We start with the root at `row = 0` and `col = (n-1)/2`. In a loop, we extract a node and its position, place its value in the matrix, and then calculate the positions for its children. The formula `res[r+1][c ± 2^(height-r-1)]` is used to find the children's columns. These children and their new positions are then added to the queue.

Here is a Java implementation:
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // Helper class to store state for BFS queue
    class State {
        TreeNode node;
        int r, c;
        State(TreeNode node, int r, int c) {
            this.node = node;
            this.r = r;
            this.c = c;
        }
    }

    public List<List<String>> printTree(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        // 1. First pass: find height using BFS
        int height = -1;
        Queue<TreeNode> bfsQueue = new LinkedList<>();
        bfsQueue.offer(root);
        while (!bfsQueue.isEmpty()) {
            height++;
            int levelSize = bfsQueue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = bfsQueue.poll();
                if (node.left != null) bfsQueue.offer(node.left);
                if (node.right != null) bfsQueue.offer(node.right);
            }
        }

        // 2. Initialize matrix
        int rows = height + 1;
        int cols = (int) Math.pow(2, height + 1) - 1;
        List<List<String>> res = new ArrayList<>();
        for (int i = 0; i < rows; i++) {
            res.add(new ArrayList<>(Collections.nCopies(cols, "")));
        }

        // 3. Second pass: fill matrix using BFS
        Queue<State> stateQueue = new LinkedList<>();
        stateQueue.offer(new State(root, 0, (cols - 1) / 2));

        while (!stateQueue.isEmpty()) {
            State current = stateQueue.poll();
            TreeNode node = current.node;
            int r = current.r;
            int c = current.c;

            res.get(r).set(c, String.valueOf(node.val));

            if (r < height) {
                int offset = (int) Math.pow(2, height - r - 1);
                if (node.left != null) {
                    stateQueue.offer(new State(node.left, r + 1, c - offset));
                }
                if (node.right != null) {
                    stateQueue.offer(new State(node.right, r + 1, c + offset));
                }
            }
        }

        return res;
    }
}
```
### Algorithm
1. **Calculate Height:** Traverse the tree using Breadth-First Search (BFS) to determine its maximum height. This is done by iterating level by level and counting the levels.
2. **Initialize Matrix:** Calculate the dimensions of the output matrix: `rows = height + 1` and `cols = 2^(height+1) - 1`. Create a `rows x cols` matrix and initialize all its cells with an empty string `""`.
3. **Fill Matrix:** Perform another BFS traversal. This time, use a queue to store not just the tree nodes, but also their corresponding `(row, col)` coordinates in the matrix. 
4. **Queue State:** A custom class or a simple data structure can be used to hold the state `(TreeNode node, int row, int col)` in the queue.
5. **Placement Logic:** Start by adding the root node with its initial position `(0, (cols-1)/2)` to the queue. In each step of the BFS, dequeue a state, place the node's value in the matrix at `[row][col]`, and then enqueue its left and right children with their calculated positions. The position of a child is determined by an offset from the parent's column, calculated as `2^(height - row - 1)`.

## Two-Pass Depth-First Search (DFS)
This approach is conceptually similar to the BFS-based one, also employing a two-pass strategy. However, it uses Depth-First Search (DFS) implemented with recursion for both passes. The first pass recursively calculates the tree's height. The second pass recursively traverses the tree to place each node's value into the correct position in the pre-initialized matrix.
**Time:** O(H * 2^H), where H is the height of the tree. The complexity analysis is identical to the BFS approach. The time is dominated by creating and initializing the large output matrix. · **Space:** O(H * 2^H), where H is the height of the tree. The space is dominated by the output matrix. The auxiliary space for the recursion call stack is O(H).
**Pros:** The recursive implementation is often more concise and can be considered more elegant.; The auxiliary space for the recursion call stack is O(H), which is generally smaller than the O(W) space for a BFS queue, especially for full or complete binary trees. This makes it more memory-efficient for the traversal part.
**Cons:** For extremely deep trees, deep recursion could theoretically lead to a stack overflow error. However, this is not a concern given the problem's constraint on tree depth (<= 10).
### Explanation
This method leverages the elegance of recursion to solve the problem. The structure remains two-pass: determine height, then fill the matrix.

**1. Height Calculation (DFS):**
A recursive function is a classic way to find the height of a tree. The function `getHeight(node)` returns -1 for a null node. Otherwise, it returns 1 plus the maximum height of its left and right subtrees. This naturally explores the longest path to a leaf.

**2. Matrix Initialization:**
This step is identical to the previous approach. The height `H` determines the matrix dimensions `m = H + 1` and `n = 2^(H+1) - 1`.

**3. Filling the Matrix (DFS):**
A recursive `fill` function is defined to handle the placement. The state (`node`, `row`, `col`) is managed by the function parameters and the call stack. The function places the current node's value, then calls itself for the left and right children with their updated positions. The `height` of the overall tree must be passed through the recursion to correctly calculate the column offset at each level.

This DFS approach is often more concise and can be more space-efficient in terms of auxiliary memory (call stack vs. queue).

Here is a Java implementation:
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<String>> printTree(TreeNode root) {
        // 1. First pass: find height
        int height = getHeight(root);
        if (height < 0) return new ArrayList<>();

        // 2. Initialize matrix
        int rows = height + 1;
        int cols = (int) Math.pow(2, height + 1) - 1;
        List<List<String>> res = new ArrayList<>();
        for (int i = 0; i < rows; i++) {
            res.add(new ArrayList<>(Collections.nCopies(cols, "")));
        }

        // 3. Second pass: fill matrix recursively
        fill(res, root, 0, (cols - 1) / 2, height);
        
        return res;
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return -1;
        }
        return 1 + Math.max(getHeight(node.left), getHeight(node.right));
    }

    private void fill(List<List<String>> res, TreeNode node, int r, int c, int height) {
        if (node == null) {
            return;
        }
        
        res.get(r).set(c, String.valueOf(node.val));
        
        if (r < height) {
            int offset = (int) Math.pow(2, height - r - 1);
            fill(res, node.left, r + 1, c - offset, height);
            fill(res, node.right, r + 1, c + offset, height);
        }
    }
}
```
### Algorithm
1. **Calculate Height (Recursive):** Define a recursive helper function `getHeight(node)`. The base case is a null node, which has a height of -1. For a non-null node, the height is `1 + max(getHeight(node.left), getHeight(node.right))`. Call this on the root to find the tree's height.
2. **Initialize Matrix:** This step is identical to the BFS approach. Calculate `rows` and `cols` from the height and create an empty `rows x cols` matrix.
3. **Fill Matrix (Recursive):** Define a second recursive helper function, `fill(node, row, col)`. This function takes the current node and its `(row, col)` position.
4. **Placement Logic:** Inside `fill`, place the current node's value at `matrix[row][col]`. Then, calculate the offset for its children using the formula `2^(height - row - 1)`. Make two recursive calls: one for the left child at `(row + 1, col - offset)` and one for the right child at `(row + 1, col + offset)`.
5. **Initial Call:** Start the process by calling `fill` for the root node with its initial position `(0, (cols-1)/2)`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List < List < String >> printTree ( TreeNode root ) { int h = height ( root ); int m = h + 1 , n = ( 1 << ( h + 1 )) - 1 ; String [][] res = new String [ m ][ n ]; for ( int i = 0 ; i < m ; ++ i ) { Arrays . fill ( res [ i ], "" ); } dfs ( root , res , h , 0 , ( n - 1 ) / 2 ); List < List < String >> ans = new ArrayList <>(); for ( String [] t : res ) { ans . add ( Arrays . asList ( t )); } return ans ; } private void dfs ( TreeNode root , String [][] res , int h , int r , int c ) { if ( root == null ) { return ; } res [ r ][ c ] = String . valueOf ( root . val ); dfs ( root . left , res , h , r + 1 , c - ( 1 << ( h - r - 1 ))); dfs ( root . right , res , h , r + 1 , c + ( 1 << ( h - r - 1 ))); } private int height ( TreeNode root ) { if ( root == null ) { return - 1 ; } return 1 + Math . max ( height ( root . left ), height ( root . right )); } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * 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: vector < vector < string >> printTree ( TreeNode * root ) { int h = height ( root ); int m = h + 1 , n = ( 1 << ( h + 1 )) - 1 ; vector < vector < string >> ans ( m , vector < string > ( n , "" )); dfs ( root , ans , h , 0 , ( n - 1 ) / 2 ); return ans ; } void dfs ( TreeNode * root , vector < vector < string >>& ans , int h , int r , int c ) { if ( ! root ) return ; ans [ r ][ c ] = to_string ( root -> val ); dfs ( root -> left , ans , h , r + 1 , c - pow ( 2 , h - r - 1 )); dfs ( root -> right , ans , h , r + 1 , c + pow ( 2 , h - r - 1 )); } int height ( TreeNode * root ) { if ( ! root ) return - 1 ; return 1 + max ( height ( root -> left ), height ( root -> right )); } };
```

### Python

```python
# 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
```