Workspace

Problem workspace

3 day streakD

Vertical Order Traversal

HardTreesViews

The challenge

Group nodes by vertical column, ordering each column by row, then value for position ties.

Root is (row 0, column 0); left changes column by −1 and right by +1. This lesson uses value-sorted ties.

Example

In the first example, values 9 and 5 share (row 2, column 0). Output: [[4], [2], [1,5,9], [3], [6]].

Use the walkthrough below to inspect the input and each state change.

See Vertical traversal, step by step

Follow the branches. Watch the state change.

7 input nodesL = left · R = right
Inspect the input.Labels identify node objects; numbers are their values. Left and right child pointers define the tree. Node labels identify objects; numbers show their values. The pointer table below provides the same structure in text.LRLRLR4D2B9E1A · root5F3C6G
CurrentProcessedPending
View child pointers & node state
Node state · null means no child
NodeValueLeftRightState
A1BC—
B2DE—
C3FG—
D4nullnull—
E9nullnull—
F5nullnull—
G6nullnull—
Step 01 / 13

Inspect the input.

Labels identify node objects; numbers are their values. Left and right child pointers define the tree.

root = A:1
View original input

A:1 [L:B, R:C] · B:2 [L:D, R:E] · C:3 [L:F, R:G] · D:4 [L:null, R:null] · E:9 [L:null, R:null] · F:5 [L:null, R:null] · G:6 [L:null, R:null]

Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.

Put it into code

Turn geometry into sortable (column, row, value) records.

Nodes store value, left, and right. C++ uses C++17 or later.

from collections import deque

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def vertical_order(root):
    entries = []
    def visit(node, row, col):
        if node is None:
            return
        entries.append((col, row, node.value))
        visit(node.left, row + 1, col - 1)
        visit(node.right, row + 1, col + 1)
    visit(root, 0, 0)
    entries.sort()
    out, previous = [], None
    for col, row, value in entries:
        if col != previous:
            out.append([])
            previous = col
        out[-1].append(value)
    return out

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap