Print Binary Tree - Leetcode Solution

Problem Statement:

Given the root of a binary tree, print its nodes in a binary tree format.

Example 1:

    Input: root = [1,2,3,null,4]
    
    Output:
    1
    |
    ├─ 2
    |   └─ 4
    |
    └─ 3

Example 2:

    Input: root = [1,null,2]
    
    Output:
    1
    |
    └─ 2

Solution:

To solve this problem, we can use a DFS approach and print each node of the binary tree row-wise.

First, let's define a recursive function, printTreeHelper(), which takes in the root of the binary tree, the starting index, and ending index of the current row, the current depth of the binary tree, and a 2D array to store the results.

In the printTreeHelper() function, we first check if the root is null, return if it is. Then, we calculate the mid index of the current row using the start and end index. We then add the value at the mid index of the current row to the result 2D array, at the position (depth, mid). After that, we call the printTreeHelper() function recursively for the left and right subtree, passing in the updated indices and depth.

Once the printTreeHelper() function completes, we create a result array with the dimensions (depth of binary tree x (2^depth - 1)). We then iterate through the 2D result array and add the elements to the final result array in the correct format, taking care to add appropriate padding or spacing between nodes.

Here is the Python code to implement the above approach:

def printTree(self, root: TreeNode) -> List[List[str]]:
    
    def printTreeHelper(root, start, end, depth, res):
        if not root:
            return
        mid = (start + end) // 2
        res[depth][mid] = str(root.val)
        printTreeHelper(root.left, start, mid - 1, depth + 1, res)
        printTreeHelper(root.right, mid + 1, end, depth + 1, res)
    
    def getDepth(root):
        if not root:
            return 0
        return 1 + max(getDepth(root.left), getDepth(root.right))
    
    depth = getDepth(root)
    res = [["" for _ in range(2 ** depth - 1)] for _ in range(depth)]
    printTreeHelper(root, 0, 2 ** depth - 1, 0, res)
    return res

Time Complexity:

The time complexity of this solution is O(nlogn), where n is the number of nodes in the binary tree. This is because we visit each node once during the DFS traversal, and the DFS traversal takes O(logn) time in the worst case for a balanced binary tree.

Space Complexity:

The space complexity of this solution is O(n), where n is the number of nodes in the binary tree. This is because we use a 2D array of size (depth x (2^depth - 1)) to store the result.

1