algoadvance

Given the root of a binary tree, you need to construct a 2D list that contains the values of the tree nodes in a specific format. The format for constructing the 2D list is as follows:

• The height of the binary tree is height.
• The width of the 2D list is 2^height - 1.
• The nodes are to be printed in a manner such that the root is centered in the top row, and each child node is centered below its parent. Empty cells are represented by "".

Clarifying Questions

1. Input Constraints
   • What is the range of the number of nodes in the tree?
   • Can the tree be empty?
2. Output Constraints
   • Should the nodes be directly translated into strings?
   • How precisely should the empty cells be represented?

Strategy

1. Determine the Height
   • Traverse the tree to compute its height.
2. Initialize the 2D List
   • Use the height to calculate the width of the 2D list and initialize each cell to "".
3. Fill the List
   • Use a recursive function to place each node in its correct position. The position of the node is determined by the properties of the tree and the specific format required.
4. Return the List
   • After filling the 2D list as per the specification, return it.

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def printTree(root: TreeNode):
    # Function to compute the height of the tree
    def getHeight(node):
        if not node:
            return 0
        return 1 + max(getHeight(node.left), getHeight(node.right))

    # Function to fill the 2D list
    def fill(res, node, row, left, right):
        if not node:
            return
        mid = (left + right) // 2
        res[row][mid] = str(node.val)
        fill(res, node.left, row + 1, left, mid - 1)
        fill(res, node.right, row + 1, mid + 1, right)

    # Step 1: Compute the height of the tree
    height = getHeight(root)

    # Step 2: Initialize the 2D list
    width = (2 ** height) - 1
    res = [["" for _ in range(width)] for _ in range(height)]

    # Step 3: Fill the 2D list with tree nodes
    fill(res, root, 0, 0, width - 1)

    return res

Detailed Explanation

1. Calculate the Height:
   • The getHeight function computes the height of the tree by recursively finding the maximum height between the left and right subtrees and adding 1 for the current node.
2. Initialize the 2D List:
   • The height (height) is used to determine the number of rows.
   • The width of the 2D list is calculated as 2^height - 1.
   • The 2D list res is initialized with "" in all cells.
3. Fill the List:
   • The fill function places each node value in the correct position.
   • The middle index between left and right is where the current node’s value should be placed.
   • The function calls itself recursively to place the left and right children.
4. Return the List:
   • Finally, return the populated 2D list.

Time Complexity

• Height Calculation: O(N), where N is the number of nodes in the tree.
• Filling 2D List: Each node is placed in the list once, resulting in O(N).
• Overall Complexity: The overall time complexity is O(N).

This approach ensures that each node is correctly positioned within the constraints of the specified 2D list format.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?