Practice › Trees
Vertical Order Traversal
Medium · Trees · Asked at Amazon, Meta, Microsoft, Google
Place the root at row 0, column 0; a left child is at (row + 1, column − 1) and a right child at (row + 1, column + 1). Print the columns from left to right, one per line. Inside a column, order nodes by row, and nodes at the same row and column by value.
Input
First line: k. Second line: k values — the tree in level order, -1 means no node.
Output
One line per column.
Constraints
- 1 ≤ number of nodes ≤ 10^4
Collect (column, row, value) for every node, sort the triples, then group by column.
Example 1
Input
7 3 9 20 -1 -1 15 7
Output
9 3 15 20 7
Example 2
Input
7 1 2 3 4 6 5 7
Output
4 2 1 5 6 3 7
Hints
- Give every node a (column, row) position with a DFS or BFS.
- Sort all (column, row, value) triples; then print one line per column.
Approach
Traverse the tree once and record (column, row, value) for each node. Sorting the triples lexicographically orders them exactly as required: by column, then row, then value (the tie-break for nodes sharing a position). Walk the sorted list and start a new output line whenever the column changes.
Complexity: O(n log n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *left = nullptr, *right = nullptr;
Node(long long v) : val(v) {}
};
// Build a tree from level order where -1 means "no node".
Node *readTree() {
int k;
cin >> k;
vector<long long> v(k);
for (auto &x : v) cin >> x;
if (k == 0 || v[0] == -1) return nullptr;
Node *root = new Node(v[0]);
queue<Node *> q;
q.push(root);
int i = 1;
while (!q.empty() && i < k) {
Node *cur = q.front();
q.pop();
if (i < k && v[i] != -1) q.push(cur->left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.push(cur->right = new Node(v[i]));
i++;
}
return root;
}
vector<tuple<int, int, long long>> items;
void walk(Node *n, int c, int d) {
if (!n) return;
items.emplace_back(c, d, n->val);
walk(n->left, c - 1, d + 1);
walk(n->right, c + 1, d + 1);
}
int main() {
walk(readTree(), 0, 0);
sort(items.begin(), items.end());
for (size_t i = 0; i < items.size(); i++) {
cout << get<2>(items[i]);
bool endCol = i + 1 == items.size() || get<0>(items[i + 1]) != get<0>(items[i]);
cout << (endCol ? "\n" : " ");
}
return 0;
}Python solution
import sys
from collections import deque
sys.setrecursionlimit(100000)
class Node:
def __init__(self, val):
self.val, self.left, self.right = val, None, None
def build_tree(v):
"""Build a tree from level order where -1 means "no node"."""
if not v or v[0] == -1:
return None
root = Node(v[0])
q, i = deque([root]), 1
while q and i < len(v):
cur = q.popleft()
if i < len(v) and v[i] != -1:
cur.left = Node(v[i])
q.append(cur.left)
i += 1
if i < len(v) and v[i] != -1:
cur.right = Node(v[i])
q.append(cur.right)
i += 1
return root
data = list(map(int, sys.stdin.read().split()))
k = data[0]
root = build_tree(data[1 : 1 + k])
rest = data[1 + k :]
items, st = [], [(root, 0, 0)]
while st:
n, c, d = st.pop()
items.append((c, d, n.val))
if n.left:
st.append((n.left, c - 1, d + 1))
if n.right:
st.append((n.right, c + 1, d + 1))
items.sort()
cols = {}
for c, _, v in items:
cols.setdefault(c, []).append(v)
print("\n".join(" ".join(map(str, cols[c])) for c in sorted(cols)))Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node left, right;
Node(long v) { val = v; }
}
// Build a tree from level order where -1 means "no node".
static Node readTree(Scanner sc) {
int k = sc.nextInt();
long[] v = new long[k];
for (int i = 0; i < k; i++) v[i] = sc.nextLong();
if (k == 0 || v[0] == -1) return null;
Node root = new Node(v[0]);
ArrayDeque<Node> q = new ArrayDeque<>();
q.add(root);
int i = 1;
while (!q.isEmpty() && i < k) {
Node cur = q.poll();
if (i < k && v[i] != -1) q.add(cur.left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.add(cur.right = new Node(v[i]));
i++;
}
return root;
}
static List<long[]> items = new ArrayList<>();
static void walk(Node n, int c, int d) {
if (n == null) return;
items.add(new long[] {c, d, n.val});
walk(n.left, c - 1, d + 1);
walk(n.right, c + 1, d + 1);
}
public static void main(String[] args) {
walk(readTree(new Scanner(System.in)), 0, 0);
items.sort((a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : a[1] != b[1] ? Long.compare(a[1], b[1]) : Long.compare(a[2], b[2]));
StringBuilder sb = new StringBuilder();
for (int i = 0; i < items.size(); i++) {
sb.append(items.get(i)[2]);
boolean endCol = i + 1 == items.size() || items.get(i + 1)[0] != items.get(i)[0];
sb.append(endCol ? "\n" : " ");
}
System.out.print(sb);
}
}Solve Vertical Order Traversal online · All practice problems