Print vertical order traversal of a binary tree

Attach coordinates to nodes

Traverse the tree from (row=0, col=0): left child is (row+1,col-1) and right child is (row+1,col+1). For simple vertical order, BFS grouping by column preserves level order. For the stricter vertical traversal variant, collect (col,row,value) triples and sort by column, then row, then value so nodes sharing a location are ordered correctly.

Traversal visits every node once, O(n) time and O(n) storage; sorting triples costs O(n log n). The important clarification is the tie rule, because two nodes can share both row and column. Test an empty tree, a single node, a skewed tree, negative columns, and two nodes at the same coordinate with different values. A map keyed only by column is insufficient for the strict variant unless it additionally preserves row/value ordering. State which variant you are implementing before claiming BFS alone is enough.