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&nbsp;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.

&nbsp;
Example 1:

Input: root = [1,2]
Output: 
[["","1",""],
&nbsp;["2","",""]]


Example 2:

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


&nbsp;
Constraints:


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


class Solution:
    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
        def height(root):
            if not root:
                return 0
            return 1 + max(height(root.left), height(root.right))
        # 1. Find height of BT
        h = height(root) - 1

        rows = h + 1
        cols = pow(2, h + 1) -1
        # 2. Create a res matrix and intialize with ""
        res = [["" for _ in range(cols)] for _ in range(rows)]

        def dfs(root, r , c):
            if not root:
                return

            res[r][c] = str(root.val)
            dfs(root.left, r + 1, c - pow(2, h - r - 1))
            dfs(root.right, r + 1, c + pow(2, h - r - 1))
            return
        # 3. Fill the matrix recursively
        dfs(root, 0, (cols - 1) // 2)
        return res
class Solution {
    public List<List<String>> printTree(TreeNode root) {
        List<List<String>> res = new ArrayList();

        int height = getHeight(root);
        int row = height + 1;
        int column = (int) Math.pow(2, height+1) - 1;

        for(int k=0; k<row; k++){
            List<String> list = new ArrayList();
            for(int i=0; i<column; i++){
                list.add("");
            }
            res.add(list);
        }

        int left = 0;
        int right = column-1;
        int level=0;
        print(res, left, right, level, root);

        return res;
    }
    public void print(List<List<String>> res, int left, int right, int level, TreeNode root){
        if(root == null) return;
        int mid = left+(right-left)/2;
        res.get(level).set(mid, String.valueOf(root.val));

        print(res, left, mid-1, level+1, root.left);
        print(res, mid+1, right, level+1, root.right);
    }
    public int getHeight(TreeNode root){
        if (root==null) return -1;
        int left = getHeight(root.left);
        int right = getHeight(root.right);

        return Math.max(left, right)+1;
    }
}
class Solution {
public:
    vector<vector<string>> res;

    int height(TreeNode* root){
        if(!root)
            return 0;
        return 1 + max(height(root->left), height(root->right));
    }

    void fill(TreeNode* root, int r, int c, int h){
        if(!root)
            return;
        res[r][c] = to_string(root->val);
        fill(root->left, r + 1, c - pow(2, h - r - 1), h);
        fill(root->right, r + 1, c + pow(2, h - r - 1), h);
    }

    vector<vector<string>> printTree(TreeNode* root) {
        int h = height(root);
        int c = pow(2, h) - 1;
        res.resize(h, vector<string>(c, ""));
        fill(root, 0, (c - 1) / 2, h - 1);
        return res;
    }
};
/**
 * @param {TreeNode} root
 * @return {string[][]}
 */
var printTree = function(root) {
	// find the height of the tree
    const m = getHeight(root)
    const height = m - 1
    const n = 2**(height+1)-1
    // create an empty m by n matrix    
    const ans = []
    for (let i = 0; i<m; i++) {
        ans.push(Array(n).fill(""))
    }
    // insert the root
    ans[0][(n-1)/2] = root.val.toString()
	// insert the rest of the nodes
    format(root,0,(n-1)/2,ans,height)
    return ans
};

function getHeight(node) {
    if (!node) return 0
    const leftHeight = getHeight(node.left)+1
    const rightHeight = getHeight(node.right)+1
    return Math.max(leftHeight,rightHeight) // take the subtree with bigger height
}

function format(node,r,c,ans,height) {
    const offset = 2**(height-r-1) // calculate the common offset
    if (node.left) {
        ans[r+1][c-offset] = node.left.val.toString()
        format(node.left,r+1,c-offset,ans,height) // recurse left node
    }
    if (node.right) {
        ans[r+1][c+offset] = node.right.val.toString()
        format(node.right,r+1,c+offset,ans,height) // recurse right node
    }
}
Print Binary Tree