Why this matters
Picture a binary tree as a drawing on paper. Ask a different question: what would you see if you looked at the tree from directly above? Or from directly below? Or what does the outline of the tree look like? Each of these questions has a clear answer, and each answer is a list of node values in a specific order.
These questions come up in layout tools, in diagram code that places boxes by column, and in interview problems. They also teach a useful habit. You attach a number to every node, then group the nodes by that number. Grouping by a key is one of the most common jobs in programming.
This lesson builds on the previous one, which showed how to compare trees. Here the nodes are not compared. They are sorted into columns, then read off in order.
The idea: a column number for every node
Start with a small tree and draw it as text.
1 column 0
/ \
2 3 column -1, column 1
/ \ \
4 5 6 column -2, column 0, column 2The root is column 0. Moving to a left child subtracts 1 from the column, and moving to a right child adds 1. So:
- Node 2 is the left child of 1, so its column is 0 minus 1, which is -1.
- Node 4 is the left child of 2, so its column is -1 minus 1, which is -2.
- Node 5 is the right child of 2, so its column is -1 plus 1, which is 0.
- Node 3 is the right child of 1, so its column is 1.
- Node 6 is the right child of 3, so its column is 2.
Now group the nodes by column, from the smallest number to the largest:
column -2: 4
column -1: 2
column 0: 1 5
column 1: 3
column 2: 6Reading the groups from left to right gives the vertical order. In column 0 there are two nodes: 1 at the top and 5 further down. The rule for the order inside a column comes next.
Two terms first. A map is a container that stores pairs of a key and a value, and looks up values by key. In C++ the ordered version is std::map. It keeps its keys sorted, so when you loop over it, you get the smallest key first. Here the key is the column number, so the loop goes left to right. A queue is a line where you add items at the back and take them from the front. In C++ it is std::queue.
Order inside a column: by depth, then left to right
Two nodes can share a column. The rule for their order is: order by depth, then left to right. Depth is the number of edges from the root down to a node. The root has depth 0, its children have depth 1, and so on. Nodes that are higher up come first in their column. If two nodes in the same column have the same depth, the one on the left comes first.
A queue gives this order without extra work. If you visit the tree one level at a time, from top to bottom and from left to right within each level, and you append each node to its column as you visit it, then each column ends up sorted by depth, and nodes at the same depth come out left to right. This visit order is called breadth-first, because it sweeps across each level before going down to the next one.
The procedure is:
- Put the root and its column (0) in the queue.
- Take the front item off the queue. Append its value to its column's list.
- If the node has a left child, add the child to the back of the queue with column minus 1.
- If the node has a right child, add the child to the back of the queue with column plus 1.
- Repeat until the queue is empty.
Writing vertical_order in C++
Here is the setup, which is the same node type and helper as the previous lessons, plus the type name for the result.
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <utility>
#include <vector>
struct Node {
int value;
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
};
std::unique_ptr<Node> make(int value,
std::unique_ptr<Node> left = nullptr,
std::unique_ptr<Node> right = nullptr) {
auto node = std::make_unique<Node>();
node->value = value;
node->left = std::move(left);
node->right = std::move(right);
return node;
}
using Columns = std::map<int, std::vector<int>>;The alias Columns names the type once. It reads as "a sorted map from a column number to the list of values in that column". The list is a std::vector<int>, which grows as values are added.
Now the function itself:
Columns vertical_order(const Node* root) {
Columns columns;
if (root == nullptr) {
return columns;
}
std::queue<std::pair<const Node*, int>> pending;
pending.push({root, 0});
while (!pending.empty()) {
auto [node, column] = pending.front();
pending.pop();
columns[column].push_back(node->value);
if (node->left) {
pending.push({node->left.get(), column - 1});
}
if (node->right) {
pending.push({node->right.get(), column + 1});
}
}
return columns;
}A few lines need explanation. std::queue<std::pair<const Node*, int>> is a queue of pairs. A pair is a small holder for two values. Each pair holds a pointer to a node and that node's column. auto [node, column] = pending.front(); is a structured binding, which splits the pair into two named variables. columns[column] looks up the list for that column, and creates an empty list the first time the column appears. push_back then adds the value to the end of that list.
The function returns columns by value. The caller gets its own copy of the map, and nothing in the tree is changed.
Top view and bottom view from the same map
Once the map exists, two more views need no extra traversal.
The top view is what you see when you look down from above. For each column, the visible node is the one highest up. Because each column's list is in depth order, that node is the first item in the list.
The bottom view is what you see from below. For each column, the visible node is the deepest one. That is the last item in the list.
std::vector<int> top_view(const Columns& columns) {
std::vector<int> out;
for (const auto& [column, values] : columns) {
out.push_back(values.front());
}
return out;
}
std::vector<int> bottom_view(const Columns& columns) {
std::vector<int> out;
for (const auto& [column, values] : columns) {
out.push_back(values.back());
}
return out;
}The loop for (const auto& [column, values] : columns) visits each entry of the map in key order, so the output goes left to right. The const in front shows that the views only read the map. values.front() is the first element and values.back() is the last. Both need the list to be non-empty, which holds for every entry the map creates, since an entry is only made when a value is added to it.
Example 1: a tree with columns from -2 to 3
The first example uses tree A, which has seven nodes:
1
/ \
2 3
/ \ \
4 5 6
\
7Column numbers: 1 is at 0. 2 is at -1, 3 is at 1. 4 is at -2, and 5 is at 0, because it is the right child of 2. 6 is at 2, and 7 is at 3.
int main() {
auto a = make(1,
make(2, make(4), make(5)),
make(3, nullptr, make(6, nullptr, make(7))));
auto ca = vertical_order(a.get());
print_columns(ca);
print_vector("top view", top_view(ca));
print_vector("bottom view", bottom_view(ca));
print_vector("boundary", boundary(a.get()));
return 0;
}The helper functions print_columns and print_vector print the results. The full program at the end of this lesson includes them. Here is the output for tree A:
column -2: 4
column -1: 2
column 0: 1 5
column 1: 3
column 2: 6
column 3: 7
top view: 4 2 1 3 6 7
bottom view: 4 2 5 3 6 7
boundary: 1 2 4 5 7 6 3Check the top view by hand. Column -2 holds only 4, column -1 holds only 2, column 0 holds 1 first and 5 second, so the top is 1. The output gives 4, 2, 1, 3, 6, 7. The bottom view differs only in column 0, where the last value is 5 instead of 1.
Example 2: when two nodes share a column and a depth
Tree C is the tricky case. Here two nodes end up in column 0 at the same depth, one from the left side and one from the right.
1
/ \
2 3
\ /
4 5
/
6In this tree, 4 is the right child of 2, and 6 is the left child of 4. Node 5 is the left child of 3. The column numbers are: 2 at -1, 4 at 0, 6 at -1, 3 at 1, and 5 at 0. Column 0 holds 1, 4 and 5. Nodes 4 and 5 are both at depth 2, so the tie rule applies. Node 4 is in the left subtree of the root, so it comes first.
auto c = make(1,
make(2, nullptr, make(4, make(6))),
make(3, make(5)));
auto cc = vertical_order(c.get());
print_columns(cc);
print_vector("top view", top_view(cc));
print_vector("bottom view", bottom_view(cc));
print_vector("boundary", boundary(c.get()));Output:
column -1: 2 6
column 0: 1 4 5
column 1: 3
top view: 2 1 3
bottom view: 6 5 3
boundary: 1 2 4 6 5 3Column 0 is 1 4 5. The top view takes the first value, 1. The bottom view takes the last value, 5, which is the rightmost of the deepest nodes in that column. Column -1 holds 2 at depth 1 and 6 at depth 3, so the list is 2 6 and the bottom view shows 6.
The rule for a tie in the same column and depth is worth stating once. The breadth-first queue adds the left subtree's nodes before the right subtree's nodes at each level, so a node on the left is always appended first. The top view keeps the first of the tied nodes, which is the one on the left. The bottom view keeps the last, which is the one on the right. Any task that needs a different tie rule must change the order in which the queue is filled.
Boundary: the outline of the tree
The boundary is the outline of the tree, read counter-clockwise starting at the root. This lesson uses one common definition, and it is the one the output above follows:
- The root.
- The left edge, going down. This is the root's left child, then the left child of that node, and so on. If a node has no left child, the edge continues to its right child. Leaves (defined in step 3) are not included here.
- Every leaf, from left to right. A leaf is a node with no children. Leaves are included wherever they are in the tree.
- The right edge, going up. This is the root's right child's chain, read from the bottom to the top. Leaves are not included here, and the root is not repeated.
Three functions do the work. Each one skips leaves in the edge functions, because step 3 already adds them.
bool is_leaf(const Node* n) {
return !n->left && !n->right;
}
void add_left_edge(const Node* n, std::vector<int>& out) {
if (n == nullptr || is_leaf(n)) {
return;
}
out.push_back(n->value);
if (n->left) {
add_left_edge(n->left.get(), out);
} else {
add_left_edge(n->right.get(), out);
}
}
void add_leaves(const Node* n, std::vector<int>& out) {
if (n == nullptr) {
return;
}
if (is_leaf(n)) {
out.push_back(n->value);
return;
}
add_leaves(n->left.get(), out);
add_leaves(n->right.get(), out);
}
void add_right_edge_bottom_up(const Node* n, std::vector<int>& out) {
if (n == nullptr || is_leaf(n)) {
return;
}
if (n->right) {
add_right_edge_bottom_up(n->right.get(), out);
} else {
add_right_edge_bottom_up(n->left.get(), out);
}
out.push_back(n->value);
}
std::vector<int> boundary(const Node* root) {
if (root == nullptr) {
return {};
}
if (is_leaf(root)) {
return {root->value};
}
std::vector<int> out{root->value};
add_left_edge(root->left.get(), out);
add_leaves(root, out);
add_right_edge_bottom_up(root->right.get(), out);
return out;
}The right edge is added in a different order from the left edge. The function calls itself on the child first, then adds the current node. So the deepest node goes into the list first. That is the bottom-up order required by step 4.
Example 3: a tree with a one-sided edge
Tree B has a left chain on the left and a right chain on the right, and both chains are longer than one step.
1
/ \
2 3
/ \
4 6
/ \
7 8auto b = make(1,
make(2, make(4, make(7))),
make(3, nullptr, make(6, nullptr, make(8))));
print_vector("boundary", boundary(b.get()));Output:
boundary: 1 2 4 7 8 6 3Walk through the four steps. The root gives 1. The left edge gives 2 and 4, and 7 is a leaf, so it is skipped there. The leaves, from left to right, are 7 and 8. The right edge is the chain 3, 6, 8. Node 8 is a leaf and is skipped, leaving 6 and 3. Read bottom-up, the right edge is 6 then 3. The full list is 1, 2, 4, 7, 8, 6, 3.
The empty tree gives an empty result. vertical_order(nullptr) returns an empty map, top_view and bottom_view return empty lists, and boundary(nullptr) returns an empty list. vertical_order and boundary check for nullptr first, and the view functions loop over nothing, so the program does not crash on an empty tree.
Common mistakes
Mistake 1: depth first instead of breadth first
A common first attempt uses a recursive walk that visits the left subtree completely, then the right subtree. It looks simpler, but it breaks the depth order inside each column. Here is that version, run on a tree where the mistake shows:
void dfs(const Node* n, int column, std::map<int, std::vector<int>>& columns) {
if (n == nullptr) return;
columns[column].push_back(n->value);
dfs(n->left.get(), column - 1, columns);
dfs(n->right.get(), column + 1, columns);
}
auto root = make(1,
make(2, nullptr, make(3, nullptr, make(4, make(5)))),
make(6, make(7)));
std::map<int, std::vector<int>> columns;
dfs(root.get(), 0, columns);
print_columns(columns);Output:
column -1: 2
column 0: 1 3 5 7
column 1: 4 6Column 0 should be 1 3 7 5. Node 7 is at depth 2 and node 5 is at depth 4, so 7 must come first. The depth-first walk reaches 5 before it reaches 7, because it goes all the way down the left branch before it looks at the right one. Column 1 has the same problem: 6 is at depth 1, and it should come before 4, which is at depth 3. The fix is the queue in vertical_order.
Mistake 2: the wrong sign for a child
Adding 1 for the left child and subtracting 1 for the right child reverses the whole picture. The output then looks mirrored. A quick check is that the root's left child must appear in a column to the left of 0, so its column is negative.
Mistake 3: a const map with operator brackets
Inside a function that receives the map as const, writing columns[column] does not compile, because operator[] may add a new entry. The compiler reports it like this, trimmed to the key lines:
const_map.cpp: In function 'void add(const std::map<int, std::vector<int> >&, int, int)':
const_map.cpp:5:19: error: passing 'const std::map<int, std::vector<int> >' as 'this' argument discards qualifiers [-fpermissive]
5 | columns[column].push_back(value);Pass the map without const when you build it, as vertical_order does. Use const only in the functions that read the map, such as top_view and bottom_view.
Mistake 4: an unordered map
std::unordered_map is faster for lookups, but its loop does not go in key order. The columns would then come out in no fixed left-to-right order, and the top view and bottom view would be wrong. When the order of the keys matters, use std::map.
Mistake 5: leaves counted twice in the boundary
If the left edge and the right edge functions did not skip leaves, a leaf at the end of an edge would be added twice: once on the edge, and once in the list of leaves. In tree B, node 7 would appear twice and node 8 would appear twice. The check is_leaf at the top of each edge function prevents this.
Practice
Each exercise is followed by its answer. Work it out before you read the answer.
Exercise 1: vertical order by hand
Draw the tree make(1, make(2, make(4)), make(3, make(5))) in columns. List each column, then give the top view and the bottom view.
Show the answer
Column -2 holds 4. Column -1 holds 2. Column 0 holds 1 and 5, in that order, because 1 is higher up. Column 1 holds 3. The top view is 4 2 1 3. The bottom view is 4 2 5 3. The program printed the same values when it was run.
Exercise 2: find a column from its parent
A node sits in column -3. What column is its right child in? What column is its left child in?
Show the answer
The right child is in column -2, since the right step adds 1. The left child is in column -4, since the left step subtracts 1.
Exercise 3: boundary of a chain
Find the boundary of make(1, make(2, make(3, make(4))), nullptr).
Show the answer
The boundary is 1 2 3 4. The left edge is 2 then 3, since node 4 is a leaf and is skipped there. The only leaf is 4, and it is added in the leaves step. The root has no right child, so the right edge is empty. The program printed 1 2 3 4 for this tree.
Exercise 4: boundary with a leaf in the middle
Find the boundary of make(1, make(2), make(3, make(4), make(5, make(6)))).
Show the answer
The boundary is 1 2 4 6 5 3. The left edge is empty because the root's left child, 2, is a leaf. The leaves from left to right are 2, 4 and 6. The right edge is the chain 3, 5 with 6 a leaf, so bottom-up the edge gives 5 then 3. The program printed 1 2 4 6 5 3.
Exercise 5: why use a queue
Explain in plain words why the breadth-first queue gives the right order inside a column, and what would go wrong with a stack.
Show the answer
The queue hands out nodes in the order they were added. The root is added first, then its children, then their children, so every node at depth 1 is handed out before any node at depth 2. Inside one level, the left child is added before the right child, so left comes before right. A stack hands out the most recently added node first. That makes the walk go down one branch before it finishes the other, which is the depth-first mistake shown earlier.
Summary
- Give the root column 0, subtract 1 for a left child, and add 1 for a right child.
- Store the nodes in a
std::mapkeyed by column. Its loop visits the columns from left to right. - A queue visits the tree one level at a time, so each column lists its nodes from top to bottom.
- The top view is the first value of each column, and the bottom view is the last.
- The boundary is the root, the left edge, the leaves from left to right, and the right edge bottom-up, with leaves skipped on the edges.
Full program
The program below prints every result in this lesson. It compiles with g++ -std=c++20 -Wall -Wextra.
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <utility>
#include <vector>
struct Node {
int value;
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
};
std::unique_ptr<Node> make(int value,
std::unique_ptr<Node> left = nullptr,
std::unique_ptr<Node> right = nullptr) {
auto node = std::make_unique<Node>();
node->value = value;
node->left = std::move(left);
node->right = std::move(right);
return node;
}
using Columns = std::map<int, std::vector<int>>;
Columns vertical_order(const Node* root) {
Columns columns;
if (root == nullptr) {
return columns;
}
std::queue<std::pair<const Node*, int>> pending;
pending.push({root, 0});
while (!pending.empty()) {
auto [node, column] = pending.front();
pending.pop();
columns[column].push_back(node->value);
if (node->left) {
pending.push({node->left.get(), column - 1});
}
if (node->right) {
pending.push({node->right.get(), column + 1});
}
}
return columns;
}
std::vector<int> top_view(const Columns& columns) {
std::vector<int> out;
for (const auto& [column, values] : columns) {
out.push_back(values.front());
}
return out;
}
std::vector<int> bottom_view(const Columns& columns) {
std::vector<int> out;
for (const auto& [column, values] : columns) {
out.push_back(values.back());
}
return out;
}
bool is_leaf(const Node* n) {
return !n->left && !n->right;
}
void add_left_edge(const Node* n, std::vector<int>& out) {
if (n == nullptr || is_leaf(n)) {
return;
}
out.push_back(n->value);
if (n->left) {
add_left_edge(n->left.get(), out);
} else {
add_left_edge(n->right.get(), out);
}
}
void add_leaves(const Node* n, std::vector<int>& out) {
if (n == nullptr) {
return;
}
if (is_leaf(n)) {
out.push_back(n->value);
return;
}
add_leaves(n->left.get(), out);
add_leaves(n->right.get(), out);
}
void add_right_edge_bottom_up(const Node* n, std::vector<int>& out) {
if (n == nullptr || is_leaf(n)) {
return;
}
if (n->right) {
add_right_edge_bottom_up(n->right.get(), out);
} else {
add_right_edge_bottom_up(n->left.get(), out);
}
out.push_back(n->value);
}
std::vector<int> boundary(const Node* root) {
if (root == nullptr) {
return {};
}
if (is_leaf(root)) {
return {root->value};
}
std::vector<int> out{root->value};
add_left_edge(root->left.get(), out);
add_leaves(root, out);
add_right_edge_bottom_up(root->right.get(), out);
return out;
}
void print_vector(const char* label, const std::vector<int>& values) {
std::cout << label << ":";
for (int v : values) {
std::cout << ' ' << v;
}
std::cout << '\n';
}
void print_columns(const Columns& columns) {
for (const auto& [column, values] : columns) {
std::cout << "column " << column << ":";
for (int v : values) {
std::cout << ' ' << v;
}
std::cout << '\n';
}
}
int main() {
std::cout << "Tree A\n";
auto a = make(1,
make(2, make(4), make(5)),
make(3, nullptr, make(6, nullptr, make(7))));
auto ca = vertical_order(a.get());
print_columns(ca);
print_vector("top view", top_view(ca));
print_vector("bottom view", bottom_view(ca));
print_vector("boundary", boundary(a.get()));
std::cout << "\nTree B\n";
auto b = make(1,
make(2, make(4, make(7))),
make(3, nullptr, make(6, nullptr, make(8))));
print_vector("boundary", boundary(b.get()));
std::cout << "\nTree C\n";
auto c = make(1,
make(2, nullptr, make(4, make(6))),
make(3, make(5)));
auto cc = vertical_order(c.get());
print_columns(cc);
print_vector("top view", top_view(cc));
print_vector("bottom view", bottom_view(cc));
print_vector("boundary", boundary(c.get()));
std::cout << "\nEmpty tree\n";
auto cempty = vertical_order(nullptr);
print_vector("top view", top_view(cempty));
print_vector("boundary", boundary(nullptr));
return 0;
}Output:
Tree A
column -2: 4
column -1: 2
column 0: 1 5
column 1: 3
column 2: 6
column 3: 7
top view: 4 2 1 3 6 7
bottom view: 4 2 5 3 6 7
boundary: 1 2 4 5 7 6 3
Tree B
boundary: 1 2 4 7 8 6 3
Tree C
column -1: 2 6
column 0: 1 4 5
column 1: 3
top view: 2 1 3
bottom view: 6 5 3
boundary: 1 2 4 6 5 3
Empty tree
top view:
boundary: