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 |

Practice

1. What does vertical order traversal of a binary tree mean?

easy

A. Nodes are visited level by level from top to bottom

B. Nodes are visited in inorder (left, root, right)

C. Nodes are visited in preorder (root, left, right)

D. Nodes are grouped by their vertical columns from left to right

Solution

1. Step 1: Understand vertical order traversal concept

   Vertical order traversal groups nodes by their vertical columns, where nodes in the same vertical line share the same horizontal distance from the root.

2. Step 2: Compare with other traversals

   Level order visits nodes by depth, preorder and inorder are depth-first traversals, not grouped by vertical columns.

3. Final Answer:

   Nodes are grouped by their vertical columns from left to right -> Option D

4. Quick Check:

   Vertical order = group by vertical columns [OK]

Hint: Vertical order groups nodes by vertical columns [OK]

Common Mistakes:

• Confusing vertical order with level order traversal
• Thinking preorder or inorder is vertical order
• Ignoring horizontal distance concept

2. Which C++ data structure is best suited to store nodes grouped by their vertical columns during vertical order traversal?

easy

A. std::vector<int>

B. std::queue<int>

C. std::map

D. std::stack<int>

Solution

1. Step 1: Identify need to group nodes by vertical column

   We need a structure that maps vertical column indices (integers) to lists of node values.

2. Step 2: Choose appropriate C++ container

   std::map maps column indices to vectors of node values, maintaining sorted order of columns automatically.

3. Final Answer:

   std::map -> Option C

4. Quick Check:

   Map column index to node list = std::map [OK]

Hint: Use map to group nodes by column [OK]

Common Mistakes:

• Using vector alone loses column indexing
• Stack or queue do not map keys to values
• Using unordered_map loses column order

3. Given the binary tree:

    1
   / \
  2   3
 /     \
4       5

What is the vertical order traversal output?

medium

A. [4, 2, 1, 3, 5]

B. [4, 2, 1, 5, 3]

C. [1, 2, 3, 4, 5]

D. [2, 4, 1, 3, 5]

Solution

1. Step 1: Assign horizontal distances (HD) to nodes

   Root 1 has HD=0; left child 2 has HD=-1; right child 3 has HD=1; 4 is left of 2 so HD=-2; 5 is right of 3 so HD=2.

2. Step 2: Group nodes by HD and list in order

   HD=-2: [4], HD=-1: [2], HD=0: [1], HD=1: [3], HD=2: [5]. Combine left to right: [4, 2, 1, 3, 5].

3. Final Answer:

   [4, 2, 1, 3, 5] -> Option A

4. Quick Check:

   Vertical order = [4, 2, 1, 3, 5] [OK]

Hint: Assign horizontal distances, then list nodes left to right [OK]

Common Mistakes:

• Mixing order of nodes in same vertical column
• Ignoring horizontal distance for children
• Listing nodes by level order instead

4. Consider this code snippet for vertical order traversal:

void verticalOrder(Node* root) {
  map m;
  queue> 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) {
    for (int val : x.second) cout << val << " ";
  }
}

What is the bug in this code?

medium

A. It does not handle empty tree (root == nullptr)

B. It uses map instead of unordered_map causing wrong order

C. It pushes right child before left child in queue

D. It does not store horizontal distances correctly

Solution

1. Step 1: Check for null root before processing

   The code assumes root is not null but does not check. If root is nullptr, q.push({root, 0}) pushes null pointer causing runtime error.

2. Step 2: Verify other parts are correct

   Using map keeps columns sorted, order of pushing left then right is correct, horizontal distances are updated properly.

3. Final Answer:

   It does not handle empty tree (root == nullptr) -> Option A

4. Quick Check:

   Missing null root check causes error [OK]

Hint: Always check if root is nullptr before traversal [OK]

Common Mistakes:

• Ignoring null root causing crash
• Confusing map with unordered_map for order
• Swapping left and right child pushes

5. You want to modify vertical order traversal to print nodes sorted by their depth within each vertical column (top to bottom). Which data structure change helps achieve this?

hard

A. Use map and sort vectors after traversal

B. Use map> to store nodes by column and depth

C. Use unordered_map and sort keys later

D. Use queue> only without map

Solution

1. Step 1: Understand requirement to sort nodes by depth per column

   We need to group nodes by vertical column and also by their depth (level) to print top to bottom.

2. Step 2: Choose data structure to store nodes by column and depth

   Using map> allows mapping column -> depth -> list of nodes, preserving order in both dimensions.

3. Final Answer:

   Use map> to store nodes by column and depth -> Option B

4. Quick Check:

   Nested map for column and depth sorting [OK]

Hint: Use nested map to sort nodes by column and depth [OK]

Common Mistakes:

• Sorting vectors after traversal is inefficient
• Using unordered_map loses order
• Ignoring depth dimension in grouping