Pattern visualizer
Vertical Order Traversal of Binary Tree
Give every node an exact 2D coordinate instead of thinking about left/right moves: the root sits at (col 0, row 0), a left child is one column left and one row down, a right child is one column right and one row down. Collect every node's (col, row, val) triple with a single DFS pass, then sort the whole list by column, then row, then value — the value tiebreak is the only part a plain traversal order can't get right on its own, for the rare case where two nodes land on the exact same column and row. Animated on: root = [3,9,20,null,null,15,7] — return nodes grouped by vertical column left to right, top to bottom within a column, ties broken by value. Expected: [[9],[3,15],[20],[7]]..
Stamp every node's (col, row), then sort by col, row, value
Every node has an exact (col, row) coordinate: the root sits at (0, 0), a left move shifts col left by one and row down by one, a right move shifts col right by one and row down by one.
1FUNCTION verticalTraversal(root):2 triples <- []3 DFS(root, 0, 0, triples)4 SORT triples BY col, row, val5 RETURN GROUP triples BY col6FUNCTION DFS(node, col, row, triples):7 IF node = null: RETURN8 APPEND (col, row, node.val) TO triples9 DFS(node.left, col - 1, row + 1, triples)10 DFS(node.right, col + 1, row + 1, triples)
← / → step · space play · Home restart