How do you solve Print Binary Tree on LeetCode?

Print Binary Tree (LeetCode #655) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Understanding how to calculate the position of nodes in a matrix based on their depth is crucial.

What is the brute force solution for Print Binary Tree?

The brute force approach for Print Binary Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves creating a matrix of the required size and filling it with the tree nodes by traversing the tree level by level. This method is straightforward but inefficient due to the need for excessive space and time. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Print Binary Tree?

Print Binary Tree uses the following concepts: Tree, Depth-First Search, Breadth-First Search, Binary Tree. The recommended patterns to study are: Tree Traversal, Matrix Manipulation.

What are the interview tips for Print Binary Tree?

Always clarify the dimensions of the output matrix before starting your implementation. Consider edge cases, such as trees with only one node or very deep trees. Practice explaining your thought process as you code, as communication is key in interviews.

What are common mistakes when solving Print Binary Tree?

Not calculating the correct indices for placing nodes in the matrix. Forgetting to handle null nodes properly, resulting in incorrect matrix dimensions.

#655

Print Binary Tree

Medium

TreeDepth-First SearchBreadth-First SearchBinary TreeTree TraversalMatrix Manipulation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution constructs the matrix in a single pass by calculating the positions directly based on the depth of the tree and the current node's position. This avoids unnecessary traversals and makes it efficient.

⚙️

Algorithm

3 steps

1Step 1: Calculate the height of the tree to determine the size of the result matrix.
2Step 2: Initialize the matrix with the appropriate dimensions.
3Step 3: Use a recursive function to fill the matrix by calculating the correct position for each node based on its depth and position in the tree.

solution.py22 lines

1# Full working Python code
2from typing import List
3
4class Solution:
5    def printTree(self, root: TreeNode) -> List[List[str]]:
6        height = self.getHeight(root)
7        m, n = height + 1, (1 << height) - 1
8        res = [[''] * n for _ in range(m)]
9        self.fill(res, root, 0, 0, (n - 1) // 2)
10        return res
11
12    def fill(self, res, node, r, depth, c):
13        if not node:
14            return
15        res[r][c] = str(node.val)
16        self.fill(res, node.left, r + 1, depth + 1, c - (1 << (height - depth - 1)))
17        self.fill(res, node.right, r + 1, depth + 1, c + (1 << (height - depth - 1)))
18
19    def getHeight(self, node):
20        if not node:
21            return 0
22        return 1 + max(self.getHeight(node.left), self.getHeight(node.right))

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once, and the space complexity is O(n) due to the storage of the result matrix.

1Understanding how to calculate the position of nodes in a matrix based on their depth is crucial.
2Recursive tree traversal can simplify the process of filling the matrix.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.