655. Print Binary Tree LeetCode Solution

In this guide, you will get 655. Print Binary Tree LeetCode Solution with the best time and space complexity. The solution to Print Binary Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Print Binary Tree solution in C++
Print Binary Tree solution in Java
Print Binary Tree solution in Python
Additional Resources

655. Print Binary Tree LeetCode Solution image

Problem Statement of Print Binary Tree

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].

Complexity Analysis

Time Complexity: O(h \cdot 2^h)
Space Complexity: O(h \cdot 2^h)

655. Print Binary Tree LeetCode Solution in C++

class Solution {
 public:
  vector<vector<string>> printTree(TreeNode* root) {
    const int m = maxHeight(root);
    const int n = pow(2, m) - 1;
    vector<vector<string>> ans(m, vector<string>(n));
    dfs(root, 0, 0, ans[0].size() - 1, ans);
    return ans;
  }

 private:
  int maxHeight(TreeNode* root) {
    if (root == nullptr)
      return 0;
    return 1 + max(maxHeight(root->left), maxHeight(root->right));
  }

  void dfs(TreeNode* root, int row, int left, int right,
           vector<vector<string>>& ans) {
    if (root == nullptr)
      return;

    const int mid = (left + right) / 2;
    ans[row][mid] = to_string(root->val);
    dfs(root->left, row + 1, left, mid - 1, ans);
    dfs(root->right, row + 1, mid + 1, right, ans);
  }
};
/* code provided by PROGIEZ */

655. Print Binary Tree LeetCode Solution in Java

class Solution {
  public List<List<String>> printTree(TreeNode root) {
    final int m = maxHeight(root);
    final int n = (int) Math.pow(2, m) - 1;
    List<List<String>> ans = new ArrayList<>();
    List<String> row = new ArrayList<>();

    for (int i = 0; i < n; ++i)
      row.add("");

    for (int i = 0; i < m; ++i)
      ans.add(new ArrayList<>(row));

    dfs(root, 0, 0, n - 1, ans);
    return ans;
  }

  private int maxHeight(TreeNode root) {
    if (root == null)
      return 0;
    return 1 + Math.max(maxHeight(root.left), maxHeight(root.right));
  }

  private void dfs(TreeNode root, int row, int left, int right, List<List<String>> ans) {
    if (root == null)
      return;

    final int mid = (left + right) / 2;
    ans.get(row).set(mid, Integer.toString(root.val));
    dfs(root.left, row + 1, left, mid - 1, ans);
    dfs(root.right, row + 1, mid + 1, right, ans);
  }
}
// code provided by PROGIEZ

655. Print Binary Tree LeetCode Solution in Python

class Solution:
  def printTree(self, root: TreeNode | None) -> list[list[str]]:
    def maxHeight(root: TreeNode | None) -> int:
      if not root:
        return 0
      return 1 + max(maxHeight(root.left), maxHeight(root.right))

    def dfs(root: TreeNode | None, row: int, left: int, right: int) -> None:
      if not root:
        return

      mid = (left + right) // 2
      ans[row][mid] = str(root.val)
      dfs(root.left, row + 1, left, mid - 1)
      dfs(root.right, row + 1, mid + 1, right)

    m = maxHeight(root)
    n = pow(2, m) - 1
    ans = [[''] * n for _ in range(m)]
    dfs(root, 0, 0, len(ans[0]) - 1)
    return ans
 # code by PROGIEZ