Problem Description

The Print Binary Tree problem requires you to represent a binary tree in a 2D string array (matrix) according to specific formatting rules. The goal is to visually "print" the tree such that:

• Each row corresponds to a level of the tree.
• The root is centered at the top row, its children are placed below it, and so on.
• All rows have the same length, which is always an odd number.
• For each node, its value must be placed in the correct position so that the left and right subtrees appear symmetrically.
• Empty positions should be filled with an empty string "".

The input is the root node of a binary tree. The output is a 2D list (matrix) of strings that visually represents the tree as described.

Constraints:

• Each tree node contains an integer value.
• The number of rows is equal to the height of the tree.
• You must not reuse elements or create extra rows/columns.

Thought Process

The challenge here is to determine where each node's value should be placed in the 2D array so that the tree appears centered and visually correct. At first, you might consider a brute-force approach: traverse the tree and try to insert values row by row, but quickly realize that without knowing the total width and the correct positions, the output will not be properly formatted.

To optimize, we need to:

• Determine the height of the tree to know how many rows are needed.
• Compute the width (number of columns) required, which depends on the tree's height.
• Recursively place each node's value at the correct column index between its left and right bounds.

This leads to a recursive, divide-and-conquer approach where for each node, we calculate its position based on its subtree's range.

Solution Approach

Let's break down the solution step by step:

1. Find the height of the tree:
   • Use a simple recursive function to get the maximum depth of the tree.
   • This tells us how many rows we need in the output matrix.
2. Calculate the number of columns:
   • The width is always 2^height - 1 (always an odd number), ensuring enough space for all nodes and their positions.
3. Initialize the matrix:
   • Create a list of lists (or 2D array) filled with empty strings "" with dimensions height x width.
4. Recursive placement function:
   • Define a helper function that takes the current node, current row, and the left and right bounds of the column range.
   • Compute the middle index as (left + right) // 2 and place the node's value there.
   • Recursively place the left child in the left half, and the right child in the right half, increasing the row each time.
5. Return the matrix:
   • After the recursive placement, return the filled matrix as the result.

We use recursion because it naturally fits the tree structure, and splitting the column range ensures each subtree is centered below its parent.

Example Walkthrough

Sample Input:

        1
       / \
      2   3
       \
        4
    

Step 1: Find Height
The tree has 3 levels (height = 3).

Step 2: Calculate Width
Width = 2³ - 1 = 7.

Step 3: Initialize Matrix
Create a 3x7 matrix filled with empty strings.

Step 4: Place Values

• Place 1 at row 0, column 3 (center).
• For left child 2: row 1, columns 0-2, place at column 1.
• For right child 3: row 1, columns 4-6, place at column 5.
• For 2's right child 4: row 2, columns 2-2, place at column 2.

Final Output:

    [
      ["",  "",  "", "1", "",  "", ""],
      ["", "2", "", "", "", "3", ""],
      ["",  "", "4", "", "", "", ""]
    ]
    

Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def printTree(self, root):
        def getHeight(node):
            if not node:
                return 0
            return 1 + max(getHeight(node.left), getHeight(node.right))
        
        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)
        
        height = getHeight(root)
        width = (1 << height) - 1
        res = [["" for _ in range(width)] for _ in range(height)]
        fill(res, root, 0, 0, width - 1)
        return res
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int getHeight(TreeNode* node) {
        if (!node) return 0;
        return 1 + std::max(getHeight(node->left), getHeight(node->right));
    }
    
    void fill(vector<vector<string>>& res, TreeNode* node, int row, int left, int right) {
        if (!node) return;
        int mid = (left + right) / 2;
        res[row][mid] = to_string(node->val);
        fill(res, node->left, row + 1, left, mid - 1);
        fill(res, node->right, row + 1, mid + 1, right);
    }
    
    vector<vector<string>> printTree(TreeNode* root) {
        int height = getHeight(root);
        int width = (1 << height) - 1;
        vector<vector<string>> res(height, vector<string>(width, ""));
        fill(res, root, 0, 0, width - 1);
        return res;
    }
};
      

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public List<List<String>> printTree(TreeNode root) {
        int height = getHeight(root);
        int width = (int)Math.pow(2, height) - 1;
        List<List<String>> res = new ArrayList<>();
        for (int i = 0; i < height; i++) {
            List<String> row = new ArrayList<>();
            for (int j = 0; j < width; j++) row.add("");
            res.add(row);
        }
        fill(res, root, 0, 0, width - 1);
        return res;
    }
    
    private int getHeight(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(getHeight(node.left), getHeight(node.right));
    }
    
    private void fill(List<List<String>> res, TreeNode node, int row, int left, int right) {
        if (node == null) return;
        int mid = (left + right) / 2;
        res.get(row).set(mid, Integer.toString(node.val));
        fill(res, node.left, row + 1, left, mid - 1);
        fill(res, node.right, row + 1, mid + 1, right);
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {string[][]}
 */
var printTree = function(root) {
    function getHeight(node) {
        if (!node) return 0;
        return 1 + Math.max(getHeight(node.left), getHeight(node.right));
    }
    
    function fill(res, node, row, left, right) {
        if (!node) return;
        let mid = Math.floor((left + right) / 2);
        res[row][mid] = node.val.toString();
        fill(res, node.left, row + 1, left, mid - 1);
        fill(res, node.right, row + 1, mid + 1, right);
    }
    
    let height = getHeight(root);
    let width = (1 << height) - 1;
    let res = [];
    for (let i = 0; i < height; i++) {
        res.push(new Array(width).fill(""));
    }
    fill(res, root, 0, 0, width - 1);
    return res;
};
      

Time and Space Complexity

Brute-force approach: If you tried to simulate the output by visiting every possible position in the matrix for each node, the time complexity could be as bad as O(N*W), where N is the number of nodes and W is the width of the matrix.

Optimized approach (as above):

• Time Complexity: O(N), where N is the number of nodes. Each node is visited once to compute the height and once to fill its value in the matrix.
• Space Complexity: O(H * W), where H is the height of the tree and W is the width (2^H - 1). This is for the output matrix.

The recursion stack will also use O(H) space due to the depth of recursion.

Summary

The Print Binary Tree problem is a great exercise in combining tree traversal with careful index calculation. The key insight is to use the tree's height to determine the correct matrix size, and then recursively place each node's value at the center of its allotted range. This ensures symmetry and correctness. By leveraging recursion and simple arithmetic, the solution remains both elegant and efficient, with clear logic that closely mirrors the tree's own structure.