655. Print Binary Tree


Problem Description

The problem states that we are given a binary tree and we need to construct a 'formatted layout' of this tree in a string matrix (essentially a 2D array where each element is a string). This matrix should visually represent the structure of the binary tree according to specific rules.

  • The number of rows in the matrix (m) should be the height of the tree plus one.
  • The number of columns (n) should be 2^(height+1) - 1, where ^ denotes exponentiation.
  • The root of the binary tree should be placed in the middle of the top row of the matrix.
  • Each node thereafter is positioned based on its parent's position, considering the height and whether it's a left or right child.
  • An empty cell is represented by an empty string.

The challenge is to place the tree nodes at the correct matrix positions that represent their hierarchical structure in the tree.

Intuition

The intuition behind the solution stems from understanding two key components: binary tree traversal and the geometric progression of a complete binary tree's width at different levels.

  1. Determine Tree Height: This is the first step since the matrix dimensions depend on it. The height informs us about the number of levels in the tree and consequently the number of rows in our matrix.

  2. Calculate Matrix Dimensions: Once we have the height, we can determine how wide the matrix should be to place all nodes. We use 2^(height+1) - 1 columns, which accommodates the widest level of the tree - the last level can potentially have maximum 2^height nodes, and we need room for space between them.

  3. Binary Tree Traversal: We need to visit each node of the binary tree and place it correctly within the matrix. This is achieved using depth-first search (DFS), which allows us to go from the root down to the leaves, ensuring that we visit all nodes and can fill in the matrix from top to bottom.

  4. Node Placement: As we traverse the tree, we place nodes in their respective positions using the logic given for left and right children in the problem statement. This step is recursive, where we keep track of the current row and column, and calculate the positions for the children accordingly. The calculation for the column of a child node is based on the current node's column and involves halving the distance between nodes at the current level for each subsequent level we go down.

By combining these steps, we can fill the matrix with node values starting from the root and continuing down to the leaves following the structure of the binary tree given to us.

Solution Approach

The solution to this problem follows a recursive approach that combines depth-first search (DFS) with careful calculation of matrix positions. The core idea revolves around a DFS algorithm that traverses the binary tree starting at the root and expands down to all reachable children nodes. At each step, the algorithm marks the current node's value in the appropriate position within the result matrix. The core steps for implementing the solution include:

  1. Calculating Tree Height: Starting at the root, use a recursive helper function to determine the height of the tree, defined as the maximum depth from the root to the farthest leaf node. This is done by comparing the height of the left and right subtrees and adding one (for the current node level).

    1def height(root):
    2    if root is None:
    3        return -1
    4    return 1 + max(height(root.left), height(root.right))
  2. Initializing the Matrix: Given the height of the tree, calculate the number of rows m and columns n for the matrix. Initialize the matrix with empty strings in every cell, as these represent unfilled positions where no tree nodes have been mapped.

    1h = height(root)
    2m, n = h + 1, 2 ** (h + 1) - 1
    3ans = [[""] * n for _ in range(m)]
  3. Placing the Nodes: Using another helper function, perform DFS starting at the root. Visit each node and place it into the matrix at the correct position. The position for children nodes is determined relative to their parent:

    • The left child is positioned 2 ** (height-r-1) spaces to the left of its parent in the matrix.
    • The right child is the same distance to the right.

    This spacing ensures the tree branches visually as it is depicted in the matrix, simulating the hierarchical levels of actual binary trees. Here's how the DFS function looks:

    1def dfs(root, r, c):
    2    if root is None:
    3        return
    4    ans[r][c] = str(root.val)
    5    dfs(root.left, r + 1, c - 2 ** (h - r - 1))
    6    dfs(root.right, r + 1, c + 2 ** (h - r - 1))
  4. Start DFS: With the matrix initialized and the DFS function defined, initiate the traversal from the root, placing it in the center of the first row of the matrix, and recursively apply DFS to position all child nodes.

    1dfs(root, 0, (n - 1) // 2)
  5. Return Result Matrix: After placement of all the nodes by DFS completes, return the final matrix which now visually represents the binary tree in the specified formatted layout.

By meticulously constructing the matrix and placing each node at its respective position, this algorithm effectively formats the tree structure into a more readable and organized visual layout.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's consider a simple binary tree and walk through the solution approach to illustrate how we can construct a formatted layout of this tree in a string matrix.

1    1
2   / \
3  2   3
4 / \
54   5

For this binary tree:

  • The height is 2 (since the longest path from the root to a leaf node - which is either 1-2-4 or 1-2-5 - has 2 edges).
  • The number of rows m in the matrix is height of the tree + 1 which gives us 3.
  • The number of columns n is 2^(height + 1) - 1 which calculates to 2^(2 + 1) - 1 = 7.
  1. Calculating Tree Height:

    • Starting with the root (1), we find that it has two children.
    • For node 2, the left subtree is of height 1 (node 4) and the right subtree is of the height 1 (node 5). Adding 1 for the level of node 2, the height from node 2 is 2.
    • For node 3, there are no children, hence the height is 0.
    • Taking the maximum of these and adding 1 for the level of the root node, the height of the tree is 2.
  2. Initializing the Matrix:

    • Based on the height, our matrix dimensions are 3 (rows) x 7 (columns).
    • We initialize the matrix with empty strings.
    1[["", "", "", "", "", "", ""],
    2 ["", "", "", "", "", "", ""],
    3 ["", "", "", "", "", "", ""]]
  3. Placing the Nodes:

    • Begin with the root node (1) at r=0 and c=(7-1)//2, which is position [0][3].
    • The left child (2) goes to r+1 and c-2^(2-r-1) which is [1][1].
    • The right child (3) goes to r+1 and c+2^(2-r-1) which is [1][5].
    • For node 2, its left child (4) goes to [2][0] and right child (5) goes to [2][2].
    • Node 3 does not have children, so we don't add more nodes to the matrix.

After placing all nodes, our formatted matrix looks like this:

1[["", "", "", "1", "", "", ""],
2 ["", "2", "", "", "", "3", ""],
3 ["4", "", "5", "", "", "", ""]]
  1. Start DFS:

    • The DFS is initiated at the root and continues recursively for each child node, following the logic for placement discussed above.
  2. Return Result Matrix:

    • After the DFS completes, we end up with a matrix that visually represents the structure of our binary tree.

In this walk-through example, we have clearly demonstrated how the recursive DFS approach and careful calculation of positions can help us construct a 'formatted layout' of a binary tree.

Python Solution

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
10        # Helper function to calculate the height of the tree. 
11        # The height is the number of edges in the longest path from the root to a leaf.
12        def height(node):
13            # Base case: an empty tree has a height of -1
14            if node is None:
15                return -1
16            # The height of a node is 1 plus the maximum height of its two children
17            return 1 + max(height(node.left), height(node.right))
18
19        # Helper function for the depth-first search that will populate the answer matrix.
20        def dfs(node, row, col):
21            # If the node is null, return as there's nothing to record.
22            if node is None:
23                return
24            # Record the value of the node at the appropriate position in the matrix.
25            matrix[row][col] = str(node.val)
26            # The offset for placing the next nodes is determined by the height at that level.
27            offset = 2 ** (tree_height - row - 1)
28            # Recur for left child, updating the row and shifting the column to the left.
29            dfs(node.left, row + 1, col - offset)
30            # Recur for right child, updating the row and shifting the column to the right.
31            dfs(node.right, row + 1, col + offset)
32
33        # Calculate the height of the tree.
34        tree_height = height(root)
35        # The matrix dimensions are determined by the height of the tree.
36        rows, cols = tree_height + 1, 2 ** (tree_height + 1) - 1
37        # Initialize the matrix with empty strings.
38        matrix = [["" for _ in range(cols)] for _ in range(rows)]
39        # Starting the DFS from the root, the initial column index is the middle of the matrix.
40        dfs(root, 0, (cols - 1) // 2)
41        # Return the populated matrix after the DFS.
42        return matrix
43

Java Solution

1class Solution {
2    // This function returns a list of lists containing the string representation of the binary tree
3    public List<List<String>> printTree(TreeNode root) {
4        // Calculate the height of the binary tree
5        int height = height(root);
6        // m is the number of rows in the output matrix, which is height + 1
7        int m = height + 1;
8        // n is the number of columns in the output matrix
9        int n = (1 << (height + 1)) - 1;
10      
11        // Initialize the output matrix with empty strings
12        String[][] matrix = new String[m][n];
13        for (int i = 0; i < m; ++i) {
14            Arrays.fill(matrix[i], "");
15        }
16      
17        // Fill the matrix with the tree elements using a depth-first search approach
18        populateMatrixWithTree(root, matrix, height, 0, (n - 1) / 2);
19      
20        // Convert the 2D array into a list of lists for the final output
21        List<List<String>> result = new ArrayList<>();
22        for (String[] row : matrix) {
23            result.add(Arrays.asList(row));
24        }
25      
26        return result;
27    }
28
29    // A recursive DFS function to populate the matrix with the tree's elements
30    private void populateMatrixWithTree(TreeNode node, String[][] matrix, int totalHeight, int row, int col) {
31        if (node == null) {
32            return;
33        }
34        // Place the current node's value into the correct position in the matrix
35        matrix[row][col] = String.valueOf(node.val);
36        // Calculate the horizontal distance to the next level's child nodes
37        int offset = 1 << (totalHeight - row - 1);
38        // Recursively process the left subtree
39        populateMatrixWithTree(node.left, matrix, totalHeight, row + 1, col - offset);
40        // Recursively process the right subtree
41        populateMatrixWithTree(node.right, matrix, totalHeight, row + 1, col + offset);
42    }
43
44    // Helper function to compute the height of the binary tree
45    private int height(TreeNode node) {
46        if (node == null) {
47            // Return -1 for an empty tree, following the convention that a single node tree has a height of 0
48            return -1;
49        }
50        // Recursive call to find the maximum height from either the left or right subtrees and add 1 for the current level
51        return 1 + Math.max(height(node.left), height(node.right));
52    }
53}
54
55// The TreeNode class definition (implicit and expected by the solution)
56class TreeNode {
57    int val;
58    TreeNode left;
59    TreeNode right;
60
61    TreeNode() {}
62
63    TreeNode(int val) {
64        this.val = val;
65    }
66
67    TreeNode(int val, TreeNode left, TreeNode right) {
68        this.val = val;
69        this.left = left;
70        this.right = right;
71    }
72}
73

C++ Solution

1#include <vector>
2#include <string>
3#include <cmath>
4#include <algorithm>
5
6// Definition for a binary tree node.
7struct TreeNode {
8    int val;
9    TreeNode *left;
10    TreeNode *right;
11    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
13};
14
15class Solution {
16public:
17    // This function formats and prints a binary tree as a 2D vector (m rows, n columns)
18    vector<vector<string>> printTree(TreeNode* root) {
19        // Calculate the height of the tree and determine the matrix dimensions
20        int treeHeight = getHeight(root);
21        int rows = treeHeight + 1;
22        int columns = (1 << (treeHeight + 1)) - 1;
23        vector<vector<string>> formattedTree(rows, vector<string>(columns, ""));
24
25        // Call recursive helper function to fill the matrix
26        populateFormattedTree(root, formattedTree, treeHeight, 0, (columns - 1) / 2);
27        return formattedTree;
28    }
29
30private:
31    // This recursive helper function populates the matrix with node values
32    void populateFormattedTree(TreeNode* node, vector<vector<string>>& formattedTree,
33                               int treeHeight, int currentRow, int currentColumn) {
34        // Base case: Null check
35        if (!node) return;
36
37        // Fill the current cell with the node's value
38        formattedTree[currentRow][currentColumn] = std::to_string(node->val);
39
40        // Calculate the offset for child nodes in the next row
41        int offset = 1 << (treeHeight - currentRow - 1);
42      
43        // Populate left subtree
44        populateFormattedTree(node->left, formattedTree,
45                              treeHeight, currentRow + 1, currentColumn - offset);
46        // Populate right subtree
47        populateFormattedTree(node->right, formattedTree,
48                              treeHeight, currentRow + 1, currentColumn + offset);
49    }
50
51    // This function calculates the height of the binary tree
52    int getHeight(TreeNode* node) {
53        // Base case: Null check (leaf nodes have height -1)
54        if (!node) return -1;
55
56        // Return the height of the node which is 1 + max of the heights of its children
57        return 1 + std::max(getHeight(node->left), getHeight(node->right));
58    }
59};
60

Typescript Solution

1// Type definition for binary tree nodes.
2type TreeNode = {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6};
7
8// Calculate the height of the binary tree.
9const getHeight = (node: TreeNode | null, level: number): number => {
10    if (node == null) {
11        return level - 1;
12    }
13    return Math.max(getHeight(node.left, level + 1), getHeight(node.right, level + 1));
14};
15
16// DFS traversal: fill the resulting array with node values.
17const fillTree = (node: TreeNode | null, row: number, col: number, level: number, res: string[][]) => {
18    if (node === null) {
19        return;
20    }
21    res[row][col] = node.val.toString();
22    const offset = 2 ** (level - row - 1);
23    fillTree(node.left, row + 1, col - offset, level, res);
24    fillTree(node.right, row + 1, col + offset, level, res);
25};
26
27// Main function to format a binary tree into a string matrix.
28const printTree = (root: TreeNode | null): string[][] => {
29    // Determine the height of the tree for matrix dimensions.
30    const height = getHeight(root, 0);
31    const rows = height + 1;
32    const cols = 2 ** (height + 1) - 1;
33    // Initialize the matrix with empty strings.
34    const result: string[][] = Array.from({ length: rows }, () => new Array(cols).fill(''));
35
36    // Start DFS traversal from the root at the center of the matrix.
37    fillTree(root, 0, (cols - 1) >> 1, height, result);
38  
39    return result;
40};
41

Time and Space Complexity

The given Python code is designed to print a binary tree in a 2D layout where each level of the tree occupies one row of the output, and positions within that row reflect the structure of the tree. Let's analyze the time and space complexities of the code:

Time Complexity:

The function height calculates the height of the tree which has a time complexity of O(n), where n is the number of nodes in the tree. This is because it traverses every node exactly once to determine the tree's height.

The function dfs (depth-first search) prints each node exactly once. Given that there are n nodes and each is visited once, the time complexity for this function is also O(n).

However, when calculating the total time complexity, we must consider the dimensions of the ans list, which acts as the output matrix. The ans list has dimensions m by n, where m is the height of the tree (O(log(n))) and n is 2^(h+1) - 1, which denotes the width of the output matrix.

Despite the size of the ans list, elements are only filled in during n iterations (each corresponding to a node in the tree). There are no nested loops that depend on the size of ans, so the overall time complexity remains O(n).

Space Complexity:

The space complexity of the code consists of the following parts:

  1. The space taken by the recursive call stack during the height and dfs functions. In the worst case (a skewed tree), this could be O(n).

  2. The space taken by the ans list to construct the output matrix. The size of this structure is m * n, where m = h + 1 and n = 2^(h+1) - 1. Since m is proportional to h, which is O(log(n)), and n here represents the width of the output matrix which could be at most 2^(O(log(n))), which simplifies to O(n). Therefore, the space complexity for the ans matrix is O(m * n) = O(n * 2^(log(n) + 1) - 1), which simplifies to O(n * n) - O(n) or simply O(n^2).

Combining these, the overall space complexity is O(n^2), dominated by the space required for the ans matrix.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫