Challenge - 5 Problems
Vertical Order Traversal Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of vertical order traversal for a simple binary tree
What is the output of the vertical order traversal for the given binary tree?
DSA C
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Tree structure:
// 1
// / \
// 2 3
// / \
// 4 5
// Vertical order traversal output format:
// Each vertical line printed as a list of node values from top to bottom.
// Assume vertical order traversal function returns an array of arrays representing vertical lines.
// For this tree, what is the vertical order traversal output?
// Expected output format (JSON): [[4], [2], [1], [3], [5]]Attempts:
2 left
💡 Hint
Think about the horizontal distance of each node from the root.
✗ Incorrect
Vertical order traversal groups nodes by their horizontal distance from the root. Nodes with the same horizontal distance are grouped together, ordered top to bottom.
❓ Predict Output
intermediate2:00remaining
Vertical order traversal output with nodes sharing vertical lines
What is the vertical order traversal output for the following binary tree?
DSA C
// Tree structure: // 10 // / \ // 7 4 // / \ \ // 3 11 14 // Expected output format (JSON): array of arrays representing vertical lines.
Attempts:
2 left
💡 Hint
Nodes with the same horizontal distance are grouped together in order from top to bottom.
✗ Incorrect
Node 10 is at horizontal distance 0. Node 7 is at -1, node 4 at 1. Node 3 at -2, node 11 at 0 (same as 10 but lower level), node 14 at 2.
🔧 Debug
advanced2:00remaining
Identify the error in vertical order traversal code snippet
What error will the following C code produce when performing vertical order traversal?
DSA C
void verticalOrder(struct Node* root) {
if (!root) return;
std::map<int, std::vector<int>> m;
std::queue<std::pair<struct Node*, int>> q;
q.push({root, 0});
while (!q.empty()) {
auto p = q.front();
q.pop();
struct Node* node = p.first;
int hd = p.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) {
for (int val : it.second) {
printf("%d ", val);
}
printf("\n");
}
}
// Note: This code is in C but uses C++ STL containers.Attempts:
2 left
💡 Hint
Check language compatibility of used data structures.
✗ Incorrect
The code uses C++ STL containers (std::map, std::vector, std::queue) in a C program, which is not allowed and causes compilation errors.
🧠 Conceptual
advanced2:00remaining
Understanding vertical order traversal with node levels
In vertical order traversal, when two nodes share the same vertical line and level, how should they be ordered?
Attempts:
2 left
💡 Hint
Think about how nodes are visited in a breadth-first traversal.
✗ Incorrect
When nodes share the same vertical line and level, they are ordered by the order they are visited in the traversal, which is typically the insertion order in the queue during BFS.
🚀 Application
expert2:00remaining
Number of vertical lines in a complex binary tree
Given the binary tree below, how many vertical lines will the vertical order traversal produce?
// Tree structure:
// 15
// / \
// 10 20
// / \ \
// 8 12 25
// / /
// 6 22
Provide the number of vertical lines as an integer.
Attempts:
2 left
💡 Hint
Count horizontal distances from root to leftmost and rightmost nodes.
✗ Incorrect
Horizontal distances range from -3 (node 6) to +2 (node 25), so total vertical lines = 6.