Vertical Order Traversal of Binary Tree in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare a struct for a binary tree node.

DSA C

typedef struct Node {
    int data;
    struct Node* [1];
    struct Node* right;
} Node;

Drag options to blanks, or click blank then click option'

Anext

Bleft

Cprev

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'child' or 'next' instead of 'left' for the left child pointer.

The left child pointer of the binary tree node is named left.

2fill in blank

medium

Complete the code to create a new node with given data.

DSA C

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->[1] = NULL;
    return newNode;
}

Drag options to blanks, or click blank then click option'

Achild

Bnext

Cright

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect pointer names like 'parent' or 'next'.

The right child pointer is named right and should be initialized to NULL.

3fill in blank

hard

Fix the error in the function to insert nodes in vertical order traversal map.

DSA C

void insertVertical(Node* root, int hd, map<int, vector<int>>* m) {
    if (root == NULL) return;
    (*m)[hd].push_back(root->[1]);
    insertVertical(root->left, hd - 1, m);
    insertVertical(root->right, hd + 1, m);
}

Drag options to blanks, or click blank then click option'

Adata

Bleft

Cright

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Inserting pointers instead of node data into the map.

We need to insert the node's data value into the map, not the left or right pointers.

4fill in blank

hard

Fill both blanks to complete the vertical order traversal function.

DSA C

void verticalOrderTraversal(Node* root) {
    map<int, vector<int>> m;
    int [1] = 0;
    insertVertical(root, [2], &m);
    for (auto it : m) {
        for (int val : it.second) {
            printf("%d ", val);
        }
        printf("\n");
    }
}

Drag options to blanks, or click blank then click option'

Ahd

Blevel

Cindex

Dpos

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names for horizontal distance causing confusion.

The horizontal distance variable is commonly named hd and initialized to 0.

5fill in blank

hard

Fill all three blanks to complete the main function that builds the tree and calls vertical order traversal.

DSA C

int main() {
    Node* root = createNode([1]);
    root->left = createNode([2]);
    root->right = createNode([3]);
    verticalOrderTraversal(root);
    return 0;
}

Drag options to blanks, or click blank then click option'

A1

B2

C3

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using zero or negative values for node data.

The root node is 1, left child is 2, and right child is 3 to form a simple binary tree.

Practice

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

easy

A. Nodes grouped by their vertical columns from left to right

B. Nodes grouped by their depth levels from top to bottom

C. Nodes visited in preorder traversal order

D. Nodes visited in postorder traversal order

Solution

1. Step 1: Understand vertical order traversal concept

   Vertical order traversal groups nodes by their vertical columns, where the root is at column 0, left child at column -1, right child at column +1, and so on.

2. Step 2: Compare with other traversal types

   Depth levels group nodes horizontally, preorder and postorder are depth-first traversals, not vertical grouping.

3. Final Answer:

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

4. Quick Check:

   Vertical order = vertical columns grouping [OK]

Hint: Vertical order groups nodes by columns, not levels or order [OK]

Common Mistakes:

• Confusing vertical order with level order traversal
• Thinking preorder or postorder is vertical order
• Mixing horizontal levels with vertical columns

2. Which data structure is commonly used to store nodes during vertical order traversal?

easy

A. Queue

B. HashMap or Dictionary

C. Stack

D. Linked List

Solution

1. Step 1: Identify storage needs for vertical order traversal

   We need to group nodes by their vertical column index, so a map (like HashMap or Dictionary) is used to store lists of nodes per column.

2. Step 2: Understand role of other data structures

   Queue is used for level order traversal but not for grouping columns; stack and linked list do not directly map columns to nodes.

3. Final Answer:

   HashMap or Dictionary -> Option B

4. Quick Check:

   Use map to group nodes by column [OK]

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

Common Mistakes:

• Using stack instead of map for grouping
• Confusing queue usage for traversal with storage
• Not grouping nodes by column properly

3. What is the output of vertical order traversal for this tree?

    1
   / \
  2   3
 / \   \
4   5   6

medium

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

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

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

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

Solution

1. Step 1: Assign vertical columns to each node

   Root 1 is at column 0; 2 is at -1; 3 is at +1; 4 is at -2; 5 is at 0; 6 is at +2.

2. Step 2: Group nodes by columns and read left to right

   Column -2: [4], -1: [2], 0: [1,5], 1: [3], 2: [6]. Reading in order: 4, 2, 1, 5, 3, 6.

3. Final Answer:

   [4, 2, 1, 5, 3, 6] -> Option D

4. Quick Check:

   Group by columns left to right [OK]

Hint: Assign columns: left -1, right +1; group and read left to right [OK]

Common Mistakes:

• Mixing order of nodes in same column
• Ignoring multiple nodes in one column
• Reading nodes top-down instead of column-wise

4. Identify the error in this vertical order traversal code snippet:

void verticalOrder(Node* root) {
  map nodes;
  queue> q;
  q.push({root, 0});
  while (!q.empty()) {
    auto p = q.front(); q.pop();
    nodes[p.second].push_back(p.first->data);
    if (p.first->left) q.push({p.first->left, p.second - 1});
    if (p.first->right) q.push({p.first->right, p.second + 1});
  }
  for (auto it : nodes) {
    for (int val : it.second) {
      cout << val << " ";
    }
  }
}

medium

A. Not sorting nodes inside each column before printing

B. Using map instead of unordered_map causes slower performance

C. Missing check if root is NULL before pushing to queue

D. Incorrect decrement and increment of column index for children

Solution

1. Step 1: Check initial queue push

   The code pushes root to queue without checking if root is NULL, which can cause runtime error if tree is empty.

2. Step 2: Verify other parts

   Column indices are correctly updated; map usage is valid; sorting nodes inside columns is optional depending on problem.

3. Final Answer:

   Missing check if root is NULL before pushing to queue -> Option C

4. Quick Check:

   Always check root != NULL before queue push [OK]

Hint: Check root != NULL before queue push to avoid errors [OK]

Common Mistakes:

• Ignoring NULL root causing crash
• Thinking map usage is incorrect
• Assuming sorting inside columns is mandatory

5. Given a binary tree, how would you modify vertical order traversal to print nodes sorted by their row (depth) within each vertical column?

hard

A. Store nodes in map>> with (row, value) and sort by row before printing

B. Use a stack instead of queue to traverse nodes depth-first

C. Ignore row and print nodes in order they appear in queue

D. Use unordered_map and sort keys before printing

Solution

1. Step 1: Understand requirement to sort by row within columns

   We need to track both column and row (depth) for each node to sort nodes vertically and then by depth.

2. Step 2: Use map with pairs and sort

   Store nodes in map keyed by column with vector of (row, value) pairs. Sort vector by row before printing to get correct order.

3. Final Answer:

   Store nodes in map<int, vector<pair<int,int>>> with (row, value) and sort by row before printing -> Option A

4. Quick Check:

   Track row and column, sort by row inside columns [OK]

Hint: Track row with column, sort nodes by row inside each column [OK]

Common Mistakes:

• Not tracking row, so nodes unordered by depth
• Using stack breaks level order needed for row tracking
• Ignoring sorting inside columns