Tree Columns With Ties

Hard

You are given the root of a binary tree. Draw the tree on a grid: the root sits in row 0, column 0, and for a node in row r, column c, its left child sits in row r + 1, column c - 1 and its right child in row r + 1, column c + 1. For every column, from the leftmost to the rightmost, list the values of its nodes from top to bottom. When several nodes land in the same cell (same row and same column), list them in increasing order of value. Return the list of columns.

Example 1

root=tree_node([5, 2, 8, 1, 4, 6, 9]) → [[1], [2], [5, 4, 6], [8], [9]]

Column 0 holds the root 5 (row 0) plus 4 and 6, both in row 2. The root is higher, so it comes first, while 4 and 6 share a cell and go in increasing order.

Example 2

root=tree_node([5, 2, 8, 1, 6, 4, 9]) → [[1], [2], [5, 4, 6], [8], [9]]

Here 6 and 4 have swapped places, but they share a cell, so the answer stays the same.

Example 3

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

The root is in column 0 and its right child in column 1.

Constraints

1 ≤ number of nodes ≤ 1000
0 ≤ Node.val ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Breadth-First Search Hash Table Binary Tree Sorting

Similar problems

Tree Columns, Top Down Medium Pair Sum in a Search Tree Easy Smallest Cover of the Bottom Row Medium Where the Deepest Leaves Meet Medium Hops Between Two Keys Medium

Input

root=tree_node([5, 2, 8, 1, 4, 6, 9])

Expected

[[1], [2], [5, 4, 6], [8], [9]]

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