> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/601-700/print-binary-tree.md).

# 655. Print Binary Tree

### Description

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

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

### Links

* Binarysearch
* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/print-binary-tree/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** root = \[1, 2]

<div align="left"><img src="/files/-MkkX1Yp-A_7TQDfY_gh" alt=""></div>

**Output:**

\[

\["", "1", ""],

\["2", "", ""]

]
{% endtab %}

{% tab title="Example 2" %}
**Input:** root = \[1, 2, 3, null, 4]

<div align="left"><img src="/files/-MkkXP5PHroSO4bBNTBY" alt=""></div>

**Output:**

\[

\["", "", "", "1", "", "", ""],

\["", "2", "", "", "", "3", ""],

\["", "", "4", "", "", "", ""]

]
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="TreeNode" %}

```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;
	}
}
```

{% endtab %}

{% tab title="Solution 1" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<List<String>> printTree(TreeNode root) {
        List<List<String>> resultMatrix = new ArrayList<>();
        
        if(root == null) {
            return resultMatrix;
        }
        
        int treeHeight = height(root);
        int treeBase = (1 << treeHeight) - 1;
        
        initMatrix(treeHeight, treeBase, resultMatrix);
        
        setNode(root, 0, 0, treeBase, resultMatrix);
        
        return resultMatrix;
    }
    
    private void setNode(TreeNode root, int row, int low, int high, List<List<String>> matrix) {
        if(root == null) {
            return;
        }
        int mid = low + (high-low)/2;
        
        matrix.get(row).set(mid, String.valueOf(root.val));
        
        setNode(root.left, row+1, low, mid-1, matrix);
        setNode(root.right, row+1, mid+1, high, matrix);
    }
    
    private void initMatrix(int rows, int cols, List<List<String>> matrix) {
        for(int i = 0; i < rows; i++) {
            List<String> row = new ArrayList<String>();
            for(int j = 0; j < cols; j++) {
                row.add("");
            }
            matrix.add(row);
        }
    }
    
    private int height(TreeNode node) {
        if(node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*