Print Binary Tree - Practice Coding Problems

Print Binary Tree - Problem

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 2^(height+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-2^(height-r-1)] and its right child at res[r+1][c+2^(height-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.

Input & Output

Example 1 — Basic Tree

$ Input: root = [1,2,3,null,4]

› Output: [["","","","1","","",""],["","2","","","","3",""],["","","4","","","",""]]

💡 Note: Tree height is 2, so matrix is 3×7. Root 1 goes at center (0,3). Node 2 at (1,1), node 3 at (1,5), node 4 at (2,2).

Example 2 — Single Node

$ Input: root = [1]

› Output: [["1"]]

💡 Note: Single node tree has height 0, creating 1×1 matrix with just the root node.

Example 3 — Larger Tree

$ Input: root = [1,2,3,4,5,6,7]

› Output: [["","","","1","","",""],["","2","","","","3",""],["","4","","5","","6","7"]]

💡 Note: Complete binary tree with height 2. Each level uses power-of-2 spacing: level 0 spacing=4, level 1 spacing=2, level 2 spacing=1.

Constraints

The number of nodes in the tree is in the range [1, 2¹⁰]
0 ≤ Node.val ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree [1,2,3,null,4] with nodes at different levels

Calculate Positions

Use height and level to determine exact matrix positions

Matrix Output

3×7 matrix with nodes placed at calculated positions, empty strings elsewhere

Key Takeaway

🎯 Key Insight: Use the formula 2^(height-row-1) to calculate exact column positions, ensuring proper tree spacing in the matrix

Asked in

F Facebook 25 a Amazon 18 M Microsoft 15

The key insight is using the mathematical formula 2^(height-row-1) to calculate exact column positions for each node based on its level in the tree. The optimal approach uses DFS traversal to place each node at its calculated position. Time: O(n + m×k), Space: O(m×k) where m×k is the matrix size.

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Position Calculation	O(n + m×k)	O(m×k)	Use DFS traversal to place each node at its calculated position in the matrix
BFS Level-by-Level Layout	O(n + m×k)	O(m×k + w)	Use BFS to process nodes level by level, calculating positions for each level

DFS with Position Calculation — Algorithm Steps

Calculate tree height using DFS
Create matrix with dimensions (height+1) × (2^(height+1)-1)
Use DFS to place each node at calculated position
Fill remaining cells with empty strings

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Height

Determine tree height to set matrix dimensions

Create Matrix

Initialize (height+1) × (2^(height+1)-1) matrix with empty strings

DFS Placement

Visit each node and place at position using power-of-2 spacing formula

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int getHeight(struct TreeNode* node) {
    if (!node) return -1;
    int leftHeight = getHeight(node->left);
    int rightHeight = getHeight(node->right);
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

void dfs(struct TreeNode* node, char*** result, int row, int col, int height) {
    if (!node) return;
    
    sprintf(result[row][col], "%d", node->val);
    
    if (node->left) {
        dfs(node->left, result, row + 1, col - (1 << (height - row - 1)), height);
    }
    if (node->right) {
        dfs(node->right, result, row + 1, col + (1 << (height - row - 1)), height);
    }
}

char*** solution(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    
    int height = getHeight(root);
    int rows = height + 1;
    int cols = (1 << (height + 1)) - 1;
    
    *returnSize = rows;
    *returnColumnSizes = (int*)malloc(rows * sizeof(int));
    
    char*** result = (char***)malloc(rows * sizeof(char**));
    for (int i = 0; i < rows; i++) {
        (*returnColumnSizes)[i] = cols;
        result[i] = (char**)malloc(cols * sizeof(char*));
        for (int j = 0; j < cols; j++) {
            result[i][j] = (char*)malloc(20 * sizeof(char));
            strcpy(result[i][j], "");
        }
    }
    
    dfs(root, result, 0, (cols - 1) / 2, height);
    return result;
}

int main() {
    // For simplicity, we'll create a sample tree
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->right = createNode(4);
    
    int returnSize;
    int* returnColumnSizes;
    char*** result = solution(root, &returnSize, &returnColumnSizes);
    
    // Print result in JSON format
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            if (j > 0) printf(",");
            printf("\"%s\"", result[i][j]);
        }
        printf("]");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m×k)

n nodes visited twice, plus m×k matrix initialization where m is height+1 and k is 2^(height+1)-1

✓ Linear Growth

Space Complexity

O(m×k)

Matrix storage plus O(h) recursion stack where h is tree height

✓ Linear Space

34.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Position Calculation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler