Vertical Order Traversal of Binary Tree in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Vertical Order Traversal for a Simple Tree

What is the output of the vertical order traversal for the given binary tree?

DSA C++

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Tree structure:
//       1
//      / \
//     2   3
//    /     \
//   4       5

// Vertical order traversal output format: list of lists, each inner list is a vertical line from left to right

#include <iostream>
#include <vector>
#include <map>
#include <queue>

std::vector<std::vector<int>> verticalOrderTraversal(Node* root) {
    std::vector<std::vector<int>> result;
    if (!root) return result;
    std::map<int, std::vector<int>> m;
    std::queue<std::pair<Node*, int>> q;
    q.push({root, 0});
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        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& x : m) {
        result.push_back(x.second);
    }
    return result;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->right->right = new Node(5);
    auto res = verticalOrderTraversal(root);
    for (auto& line : res) {
        for (int val : line) std::cout << val << " ";
        std::cout << "| ";
    }
    return 0;
}

A 4 2 1 | 3 5 |

B 4 2 | 1 3 | 5 |

C 4 | 2 1 | 3 5 |

D 4 | 2 | 1 | 3 | 5 |

💡 Hint

Think about horizontal distances from the root and how nodes are grouped by these distances.

Nodes are grouped by their horizontal distance (hd) from the root. Left child decreases hd by 1, right child increases hd by 1. The traversal collects nodes in order of hd from left to right.

🧠 Conceptual

intermediate

Understanding Horizontal Distance in Vertical Order Traversal

In vertical order traversal of a binary tree, what does the 'horizontal distance' (hd) represent?

A The horizontal position of a node relative to the root, where left child decreases hd by 1 and right child increases hd by 1

B The depth of a node in the tree

C The vertical level of a node from the root

D The number of nodes in the subtree rooted at that node

💡 Hint

Think about how nodes are grouped vertically in the output.

Horizontal distance is used to group nodes vertically. The root has hd=0, left child hd-1, right child hd+1. This helps to collect nodes in vertical lines.

🔧 Debug

advanced

Identify the Error in Vertical Order Traversal Code

What error will the following code produce when performing vertical order traversal?

DSA C++

std::vector<std::vector<int>> verticalOrderTraversal(Node* root) {
    std::vector<std::vector<int>> result;
    if (!root) return result;
    std::unordered_map<int, std::vector<int>> m;
    std::queue<std::pair<Node*, int>> q;
    q.push({root, 0});
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        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& x : m) {
        result.push_back(x.second);
    }
    return result;
}

A No error, code runs correctly

B Output order of vertical lines is not sorted from left to right

C Runtime error due to invalid queue operations

D Compilation error due to missing include for unordered_map

💡 Hint

Consider the difference between unordered_map and map in C++.

unordered_map does not keep keys sorted, so vertical lines will be collected but output order will be unpredictable, not left to right.

🚀 Application

advanced

Vertical Order Traversal with Level Sorting

How would you modify vertical order traversal to output nodes sorted by their level (top to bottom) within each vertical line?

A Use a map<int, vector<pair<int,int>>> storing (level, node_value) and sort vectors by level before output

B Use a map<int, vector<int>> and insert nodes as they are visited in BFS order

C Use a queue and process nodes in DFS order to maintain level sorting

D Use an unordered_map and sort keys before output

💡 Hint

You need to track both horizontal distance and vertical level for sorting.

Storing pairs of (level, node_value) allows sorting nodes by level within each vertical line before output.

❓ Predict Output

expert

Output of Vertical Order Traversal with Multiple Nodes on Same Vertical and Level

Given the binary tree below, what is the output of the vertical order traversal that sorts nodes by level and then by value if levels are equal? // Tree structure: // 1 // / \ // 2 3 // / \ \ // 4 5 6 // \ \ // 7 8 // Output format: each vertical line as a list of node values separated by spaces, vertical lines separated by '| '

DSA C++

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

std::vector<std::vector<int>> verticalOrderTraversal(Node* root) {
    std::vector<std::vector<int>> result;
    if (!root) return result;
    std::map<int, std::vector<std::pair<int,int>>> m; // hd -> (level, val)
    std::queue<std::tuple<Node*, int, int>> q; // node, hd, level
    q.push({root, 0, 0});
    while (!q.empty()) {
        auto [node, hd, level] = q.front(); q.pop();
        m[hd].push_back({level, node->data});
        if (node->left) q.push({node->left, hd - 1, level + 1});
        if (node->right) q.push({node->right, hd + 1, level + 1});
    }
    for (auto& [hd, vec] : m) {
        std::sort(vec.begin(), vec.end(), [](auto& a, auto& b) {
            if (a.first == b.first) return a.second < b.second;
            return a.first < b.first;
        });
        std::vector<int> line;
        for (auto& p : vec) line.push_back(p.second);
        result.push_back(line);
    }
    return result;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(6);
    root->left->right->right = new Node(7);
    root->right->right->right = new Node(8);

    auto res = verticalOrderTraversal(root);
    for (auto& line : res) {
        for (int val : line) std::cout << val << " ";
        std::cout << "| ";
    }
    return 0;
}

A 4 | 2 | 1 3 5 | 6 7 | 8 |

B 4 | 2 | 1 5 7 | 3 | 6 8 |

C 4 | 2 | 1 5 | 3 7 | 6 | 8 |

D 4 | 2 | 1 3 5 7 | 6 8 |

💡 Hint

Sort nodes by level first, then by value if levels are equal, within each vertical line.

Nodes are grouped by hd. Within each hd, nodes are sorted by level ascending, then by value ascending if levels tie. This produces the output: 4 | 2 | 1 5 | 3 7 | 6 | 8 |