Column by column
Add up the values in each vertical column of a tree, by giving every node a column number - one less going left, one more going right - and totalling per column. About 14 minutes.
A column number for every node
Draw the tree and imagine vertical lines. All nodes on the same line are in the same column. The root is in column 0. Going to a left child moves you one column left, so subtract one. Going to a right child moves one column right, so add one.
A node can share a column with nodes in other subtrees, for example the right child of a left child shares the root's column.
sums = {}
sums[-1] = sums.get(-1, 0) + 9
sums[0] = sums.get(0, 0) + 3- totals
- -2: 1
1 is two steps left of the root, in column -2. Total: 1.
Totals from left to right
Carry the column number along with each node in the queue. When a node is taken, add its value to the total of its column in a map.
At the end, the keys of the map are the columns that exist. Sort them, and read off the totals in that order. The leftmost column comes first. An empty tree has no columns, so the answer is an empty list.
cols = sorted(sums) # left to right
A node is in column 2. In which column is its left child's right child?
- AColumn 2
- BColumn 3
- CColumn 1
Show the answer
Column 2. Left is minus one, then right is plus one, which returns to column 2.
Vertical column sums
Given the root of a binary tree, assign the root to column 0, each left child to the column one less than its parent's, and each right child to the column one more. Return an array with the sum of the values in each column, from the leftmost column to the rightmost. An empty tree gives an empty array.
root = [3, 9, 20, null, null, 15, 7] → [9, 18, 20, 7]
0 ≤ number of nodes ≤ 10,000 · -1,000 ≤ node.val ≤ 1,000