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.
View child pointers & node state
| Node | Value | Left | Right | State |
|---|---|---|---|---|
| A | 1 | B | C | — |
| B | 2 | D | E | — |
| C | 3 | F | G | — |
| D | 4 | null | null | — |
| E | 9 | null | null | — |
| F | 5 | null | null | — |
| G | 6 | null | null | — |
Inspect the input.
Labels identify node objects; numbers are their values. Left and right child pointers define the tree.
root = A:1View 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
#include <algorithm>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct Node {
long long value;
Node *left = nullptr, *right = nullptr;
explicit Node(long long v) : value(v) {}
};
vector<vector<long long>> vertical_order(Node* root) {
vector<tuple<int, int, long long>> entries;
function<void(Node*, int, int)> visit = [&](Node* n, int row, int col) {
if (!n) return;
entries.emplace_back(col, row, n->value);
visit(n->left, row + 1, col - 1);
visit(n->right, row + 1, col + 1);
};
visit(root, 0, 0);
sort(entries.begin(), entries.end());
vector<vector<long long>> out;
optional<int> previous;
for (auto [col, row, value] : entries) {
if (!previous || col != *previous) { out.push_back({}); previous = col; }
out.back().push_back(value);
}
return out;
}