We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Print Binary Tree

Difficulty: Medium

Problem 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 specific rules regarding the placement of tree nodes and empty cells.

Key Insights

  • The height of the tree determines the dimensions of the matrix: number of rows (height + 1) and number of columns (2^(height + 1) - 1).
  • The root node is placed in the middle of the top row of the matrix.
  • For each node placed in the matrix, the left and right children are positioned according to specific calculated indices based on the current node's position.
  • Empty cells in the matrix are filled with an empty string.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, as we visit each node once. Space Complexity: O(N), for storing the matrix.

Solution

To solve the problem, we utilize a breadth-first search (BFS) or depth-first search (DFS) approach to traverse the binary tree. We create a 2D list (matrix) initialized with empty strings. During the traversal, we calculate the position for each node based on its depth and the column index derived from its position in the tree. This allows us to correctly place each node in the matrix while accounting for empty spaces.

Code Solutions

def printTree(root):
    height = getHeight(root)
    m = height + 1
    n = (1 << (height + 1)) - 1  # 2^(height + 1) - 1
    res = [[""] * n for _ in range(m)]
    
    def fill(node, r, c):
        if not node:
            return
        res[r][c] = str(node.val)
        fill(node.left, r + 1, c - (1 << (height - r - 1)))
        fill(node.right, r + 1, c + (1 << (height - r - 1)))
    
    fill(root, 0, (n - 1) // 2)
    return res

def getHeight(node):
    if not node:
        return -1
    return 1 + max(getHeight(node.left), getHeight(node.right))
← Back to All Questions