Print Binary Tree - Solution & Explanation

Problem Overview: Given the root of a binary tree, return a 2D string matrix that visually represents the tree structure. The matrix width must be 2^height - 1, and each node is placed at the midpoint of its valid column range so that left and right children appear symmetrically below the parent.

Approach 1: Recursive Placement of Nodes (DFS) (Time: O(n), Space: O(n))

This approach uses Depth-First Search to place nodes directly in the correct matrix positions. First compute the tree height using a recursive traversal. The matrix dimensions become height x (2^height - 1). During DFS, each node is assigned a column based on the midpoint of its current column range [left, right]. Place the node value at that midpoint, then recursively process the left child with range [left, mid-1] and the right child with [mid+1, right]. This works because every subtree occupies exactly half of its parent’s horizontal space. The recursion naturally mirrors the structure of a Binary Tree, making the placement logic clean and predictable. This is the most common and readable solution.

Approach 2: Iterative Level Order Traversal (BFS) (Time: O(n), Space: O(n))

This version uses Breadth-First Search with a queue to process nodes level by level. After computing the tree height and initializing the matrix, push the root into a queue along with its column boundaries. Each queue entry stores (node, row, leftBound, rightBound). When processing a node, compute the midpoint column and write its value into the matrix. Then push the left and right children into the queue with updated column ranges. BFS makes the row index explicit and avoids recursion depth limits. The placement logic is the same midpoint calculation used in the DFS solution, but controlled iteratively.

Recommended for interviews: The recursive DFS placement is usually the expected solution because it maps directly to the tree structure and requires less bookkeeping. Interviewers like it because the midpoint calculation clearly shows you understand how the visual layout relates to tree height. The BFS approach is equally optimal in complexity and demonstrates familiarity with queue-based traversal, but the DFS version is typically shorter and easier to reason about.