Tree Layout Presets
Algorithm Stages
TreeMap Output Grouping
Coordinate-Mapped Nodes
Click a node to modify it. Notice how nodes snap mathematically into vertical columns based
on their HD (Horizontal Distance)!
Live Console Log
Vertical Order Traversal
Vertical Order Traversal is a tree layout algorithm that groups nodes by their Horizontal Distance (HD) from the root. Imagine drawing vertical lines down through the tree: nodes lying on the same vertical line are grouped together.
Horizontal Distance (HD)
The Root node starts at HD = 0.
A Left Child's HD = Parent's HD - 1.
A Right Child's HD = Parent's HD + 1.
Map & Queue (BFS)
A Breadth-First Search (Queue) guarantees we visit higher levels first. We use a
TreeMap (sorted map) to group nodes by HD, ensuring left-most vertical columns
are printed first.
Algorithm Implementation
import java.util.*;
class Node {
int data;
Node left, right;
Node(int data) { this.data = data; }
}
class Pair {
Node node;
int hd; // Horizontal Distance
Pair(Node node, int hd) {
this.node = node;
this.hd = hd;
}
}
public class VerticalTraversal {
public List<List<Integer>> verticalOrder(Node root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) return ans;
// TreeMap automatically sorts keys (Horizontal Distances)
Map<Integer, List<Integer>> map = new TreeMap<>();
// BFS Queue guarantees level-order (top-to-bottom) per column
Queue<Pair> q = new LinkedList<>();
q.offer(new Pair(root, 0));
while (!q.isEmpty()) {
Pair curr = q.poll();
Node node = curr.node;
int hd = curr.hd;
// Add node value to the corresponding vertical column
map.putIfAbsent(hd, new ArrayList<>());
map.get(hd).add(node.data);
if (node.left != null) {
q.offer(new Pair(node.left, hd - 1));
}
if (node.right != null) {
q.offer(new Pair(node.right, hd + 1));
}
}
// Compile final answer from sorted map
for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
ans.add(entry.getValue());
}
return ans;
}
}#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
struct Node {
int data;
Node *left, *right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
class Solution {
public:
vector<vector<int>> verticalOrder(Node* root) {
vector<vector<int>> ans;
if (!root) return ans;
// map automatically sorts by key (HD)
map<int, vector<int>> m;
queue<pair<Node*, int>> q; // pair of (Node, HD)
q.push({root, 0});
while (!q.empty()) {
auto curr = q.front();
q.pop();
Node* node = curr.first;
int hd = curr.second;
m[hd].push_back(node->data);
if (node->left) q.push({node->left, hd - 1});
if (node->right) q.push({node->right, hd + 1});
}
for (auto it : m) {
ans.push_back(it.second);
}
return ans;
}
};from collections import deque, defaultdict
class Node:
def __init__(self, val):
self.data = val
self.left = None
self.right = None
class Solution:
def verticalOrder(self, root):
if not root:
return []
columnTable = defaultdict(list)
queue = deque([(root, 0)]) # Queue stores tuples of (Node, HD)
min_hd = float('inf')
max_hd = float('-inf')
while queue:
node, hd = queue.popleft()
# Group by Horizontal Distance
columnTable[hd].append(node.data)
# Track bounds to avoid needing a sorted dictionary
min_hd = min(min_hd, hd)
max_hd = max(max_hd, hd)
if node.left:
queue.append((node.left, hd - 1))
if node.right:
queue.append((node.right, hd + 1))
# Compile result iterating from leftmost HD to rightmost HD
return [columnTable[x] for x in range(min_hd, max_hd + 1)]