A Tree Drawn on a Grid

Medium

You are given the root of a binary tree. Draw the tree as a table of strings using the rules below. Let the tree have L levels (a single root means L = 1). The table has L rows and 2^L − 1 columns, and every cell starts as the empty string "". - The root goes into the top row, exactly in the middle column. - If a node sits in row r (0-based) and column c, its left child goes into row r + 1, column c − 2^(L − r − 2), and its right child into column c + 2^(L − r − 2). - A cell holds the node's value as a string, e.g. "-3". Return the resulting table as a list of rows.

Example 1

root=tree_node([7, None, -3]) → [['', '7', ''], ['', '', '-3']]

There are two levels, so the width is 2² − 1 = 3. The root 7 sits in the middle column, and its right child -3 goes to column 2 of the next row.

Example 2

root=tree_node([5, 8, 1, 4]) → [['', '', '', '5', '', '', ''], ['', '8', '', '', '', '1', ''], ['4', '', '', '', '', '', '']]

Three levels, width 7. The root is in column 3, its children are 2 columns away (columns 1 and 5), and the grandchild 4 is 1 column left of its parent 8, in column 0.

Constraints

The tree has between 1 and 210 nodes
-99 ≤ node value ≤ 99
The tree has at most 10 levels

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Breadth-First Search Binary Tree

Similar problems

The Tree Seen From the Right Medium Tree Columns, Top Down Medium First Value on the Lowest Row Medium Largest Value on Each Tree Level Medium Insert a Tree Level Medium

Input

root=tree_node([7, None, -3])

Expected

[['', '7', ''], ['', '', '-3']]

Run checks the first 3 tests in your browser. Submit checks all 65 tests on the server, hidden ones included.