def verticalOrder(self, root):
cols = collections.defaultdict(list)
queue = [(root, 0)]
for node, i in queue:
if node:
cols[i].append(node.val)
queue += (node.left, i  1), (node.right, i + 1)
return [cols[i] for i in sorted(cols)]
Python solution

@bryan.chou.121 Yeah, I know... I just prefer focusing on the actual algorithm, so I like doing it this short way. I'm sure I've mentioned before that to my knowledge this isn't guaranteed to work, but while I'm always aware of it, I really don't feel like explaining it every time. Maybe I should just stop using it...

Ok I just wrote the two obvious clean replacements. Meh... I wish they'd just define my iteration to work.
def verticalOrder(self, root): cols = collections.defaultdict(list) queue = collections.deque([(root, 0)]) while queue: node, i = queue.popleft() if node: cols[i].append(node.val) queue += (node.left, i  1), (node.right, i + 1) return [cols[i] for i in sorted(cols)] def verticalOrder(self, root): cols = collections.defaultdict(list) queue = [(root, 0)] i = 0 while i < len(queue): node, x = queue[i] i += 1 if node: cols[x].append(node.val) queue += (node.left, x  1), (node.right, x + 1) return [cols[x] for x in sorted(cols)]

Most highly voted answers for this question are incorrect.
Given a perfect 4level binary tree, named by level: 1; 2,3; 4,5,6,7; 8,9,10,11,12,13,14,15, I got this result: [[8], [4], [2, 9, 10, 12], [1, 5, 6], [3, 11, 13, 14], [7], [15]]. See that 12 runs into a bucket ahead of 11's. I don't think that's right. The correct answer should be [[8],[4],[2,9,10],[5],[1,11,12],[6],[3,13,14],[7],[15]]. Draw the tree on a paper, you'll see.My ugly drawing is here:
http://postimg.org/image/w6yrf356n

yeah, i got the same confusion. the question actually assumes the nodes have the same width to its neighbors (which is missing in the statement), so they could cross over each other. However, if you enumerate the nodes straightly without any overlap, as drawn in the nick46's "ugly" image, the "vertical" result is totally dependent on the shape of the tree. The latter problem is far more difficult to solve.

But as @nick46 point out, how to explain
12 runs into a bucket ahead of 11's
? This is weird.....As @StefanPochmann said,
2 > 9
is through one left, one right, and the same width means with the samesteps
goes from a node. If this is kind of the definition of width, I got more confused now....

@StefanPochmann Could've done something like this:
class Solution(object): def verticalOrder(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ if not root: return [] d=collections.defaultdict(list) q=[(root,0)] for node,i in q: if node: d[i].append(node.val) q.append((node.left,i1)) q.append((node.right,i+1)) ret=[0]*len(d) diff=min(d.keys()) for k,v in d.items(): ret[k+diff]=v return ret


@StefanPochmann Don't see how it's slower considering you're using a sort function. The time complexity of mine is O(n), I doubt it's slower, unless python's timesort came into play here.

@livelearn Well, here are some test results. I created the dictionary with keys from n to n in random order and then ran mine against yours. The floats are times in seconds.
n: 1 stefan: 7.680 livelearn: 9.603 n: 10 stefan: 2.601 livelearn: 2.678 n: 100 stefan: 1.697 livelearn: 1.878 n: 1000 stefan: 1.273 livelearn: 1.932 n: 10000 stefan: 1.200 livelearn: 2.169 n: 100000 stefan: 2.198 livelearn: 4.137 n: 1000000 stefan: 3.301 livelearn: 5.604
The testing script:
from collections import defaultdict from random import shuffle from timeit import timeit def stefan(cols): return [cols[i] for i in sorted(cols)] def livelearn(d): ret=[0]*len(d) diff=min(d.keys()) for k,v in d.items(): ret[k+diff]=v return ret for e in range(7): n = 10**e r = range(n, n) shuffle(r) cols = defaultdict(list) for i in r: cols[i].append(i) ts = timeit(lambda: stefan(cols), number=10**7 / n) tl = timeit(lambda: livelearn(cols), number=10**7 / n) print 'n: %7d stefan: %6.3f livelearn: %6.3f' % (n, ts, tl)

@livelearn said in Python solution:
I could simply calculate the min in the original for loop. That could make mine faster than yours if that line is taken out.
I'm pretty sure that would make your solution slower, not faster.