# Solving Leetcode Interviews in Seconds with AI: Print Binary Tree


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "655" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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:   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].  

	# Explanation
	Here's a breakdown of the approach, complexity, and Python code for the problem:

*   **High-Level Approach:**
    *   Calculate the height of the binary tree to determine the dimensions of the result matrix.
    *   Create the result matrix filled with empty strings.
    *   Perform a recursive traversal of the tree, placing each node's value in the correct position in the matrix based on the provided formula.

*   **Complexity:**
    *   Runtime Complexity: O(N), where N is the number of nodes in the tree.
    *   Storage Complexity: O(M\*N), where M is the height + 1 of the tree and N is 2^(height+1) - 1 (the width of the matrix). This is dominated by the size of the `res` matrix.

	
	# Code
	```python
	from typing import Optional, List

# 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 get_height(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            return 1 + max(get_height(node.left), get_height(node.right))

        height = get_height(root)
        m = height
        n = 2**height - 1
        res = [[""] * n for _ in range(m)]

        def fill_matrix(node: Optional[TreeNode], r: int, c: int, height: int):
            if not node:
                return
            res[r][c] = str(node.val)
            fill_matrix(node.left, r + 1, c - 2**(height - r - 1), height)
            fill_matrix(node.right, r + 1, c + 2**(height - r - 1), height)

        fill_matrix(root, 0, (n - 1) // 2, height)
        return res
	```