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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Print Binary Tree

Number: 655

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Poynt

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 layout is defined as follows:

  • The number of rows m equals the tree’s height plus one.
  • The number of columns n equals 2^(height+1) - 1.
  • The root node is placed in the middle of the top row.
  • For a node positioned at res[r][c], its left child is placed at res[r+1][c - 2^(height - r - 1)] and its right child at res[r+1][c + 2^(height - r - 1)]. Any unused cells are filled with empty strings.

Key Insights

  • Compute the height of the binary tree to determine the dimensions of the matrix.
  • Initialize an m x n matrix filled with empty strings.
  • Use a recursive approach (depth-first search) to place each node at the correct position.
  • The correct column positions are determined by calculating an offset based on the current row and remaining depth.

Space and Time Complexity

Time Complexity: O(n) — Each node is visited once. Space Complexity: O(m*n) — For storing the result matrix, plus O(h) recursion stack where h is the tree height.

Solution

We first determine the height of the binary tree, which helps calculate the number of rows (height + 1) and columns (2^(height+1) - 1) for the output matrix. Next, we initialize the matrix with empty strings. A helper function then uses recursion to place the value of each node at its specific (r, c) position in the matrix. The left and right children are subsequently placed in the next row, with their positions offset by a computed value (2^(height - current_row - 1)). This recursive process continues until all nodes have been placed.

Code Solutions

class Solution:
    def printTree(self, root):
        # Helper function to compute the height of the binary tree.
        def getHeight(node):
            if not node:
                return -1  # Using -1 so that a leaf has height 0.
            return 1 + max(getHeight(node.left), getHeight(node.right))
        
        height = getHeight(root)
        m = height + 1
        n = (1 << (height + 1)) - 1  # Computing 2^(height+1) - 1.
        
        # Initialize the matrix with empty strings.
        res = [["" for _ in range(n)] for _ in range(m)]
        
        # Recursively fill in the matrix with node values.
        def fill(node, r, c):
            if not node:
                return
            # Place the current node's value as a string.
            res[r][c] = str(node.val)
            # Calculate the offset for child nodes.
            offset = 1 << (height - r - 1)
            if node.left:
                fill(node.left, r + 1, c - offset)
            if node.right:
                fill(node.right, r + 1, c + offset)
        
        # Start placing from the root at the middle of the top row.
        fill(root, 0, (n - 1) // 2)
        return res
← Back to All Questions