Vertical Order Traversal of Binary Tree in DSA Java - 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 following binary tree?

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

DSA Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}

// Vertical order traversal method returns list of lists of integers
// Each inner list contains nodes in one vertical column from left to right

// Assume verticalOrder(root) returns List<List<Integer>>

// For this tree, what is the vertical order traversal output?

// Output format: [[2], [1, 4], [3], [5]]

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

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

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

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

💡 Hint

Think about columns from left to right and nodes in each column top to bottom.

Vertical order groups nodes by their horizontal distance from root. Left child is one column left (-1), right child one column right (+1). Nodes in same column are listed top to bottom.

🧠 Conceptual

intermediate

Understanding Horizontal Distance in Vertical Order Traversal

In vertical order traversal, what does the 'horizontal distance' of a node represent?

A The sum of values of all nodes to the left of the current node

B The vertical level (depth) of the node in the tree

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

D The horizontal distance from the root node, where left child decreases by 1 and right child increases by 1

💡 Hint

Think about how columns are assigned in vertical order traversal.

Horizontal distance is a number assigned to each node based on its position relative to the root: root is 0, left child is parent minus 1, right child is parent plus 1.

❓ Predict Output

advanced

Output of Vertical Order Traversal with Multiple Nodes in Same Column and Row

Given the binary tree below, what is the vertical order traversal output?

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

DSA Java

/*
Vertical order traversal groups nodes by horizontal distance.
Nodes in same column are listed top to bottom.
If nodes share same row and column, order by node value ascending.
*/

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

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

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

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

💡 Hint

Remember to order nodes with same row and column by their value.

Column -2: 4
Column -1: 2
Column 0: 1 (row 0), 5 (row 2)
Column 1: 3 (row 1), 7 (row 3)
Column 2: 6

🔧 Debug

advanced

Identify the Error in Vertical Order Traversal Code Snippet

What error will this Java code snippet cause when performing vertical order traversal?

Code snippet:
```java Map> map = new TreeMap<>(); Queue queue = new LinkedList<>(); Queue cols = new LinkedList<>(); queue.add(root); cols.add(0); while (!queue.isEmpty()) { TreeNode node = queue.poll(); int col = cols.poll(); if (!map.containsKey(col)) { map.put(col, new ArrayList<>()); } map.get(col).add(node.val); if (node.left != null) { queue.add(node.left); cols.add(col - 1); } if (node.right != null) { queue.add(node.right); cols.add(col + 1); } } return map.values(); ```

A ClassCastException when adding nodes to map

B ConcurrentModificationException during iteration

C NullPointerException if root is null

D No error; code runs correctly

💡 Hint

Consider what happens if root is null before adding to queue.

The code lacks a null check for root before adding it to the queue. If root is null, queue.add(null) succeeds, but queue.poll() returns null, causing NullPointerException when accessing node.val.

🚀 Application

expert

Number of Vertical Columns in a Complex Binary Tree

Consider a binary tree where each node has either 0 or 2 children, and the tree is perfectly balanced with height 3 (root at height 0). How many vertical columns will the vertical order traversal produce?

A 7

B 8

C 15

D 5

💡 Hint

Think about horizontal distances from root in a perfect binary tree of height 3.

In a perfect binary tree of height h, horizontal distances range from -h to +h, so total columns = 2*h + 1.

Practice

1. What does Vertical Order Traversal of a binary tree mean?

easy

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

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

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

D. Nodes are grouped by their horizontal rows from top to bottom

Solution

1. Step 1: Understand vertical columns in a tree

   Vertical order groups nodes by their horizontal distance from the root, called columns.

2. Step 2: Define vertical order traversal

   Nodes in the same vertical column are collected and output from leftmost to rightmost column.

3. Final Answer:

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

4. Quick Check:

   Vertical order = group by columns [OK]

Hint: Think columns from left to right, not rows or preorder [OK]

Common Mistakes:

• Confusing vertical order with level order traversal
• Thinking vertical order is preorder or inorder traversal
• Mixing horizontal rows with vertical columns

2. Which Java data structure is best to store nodes grouped by their vertical column during vertical order traversal?

easy

A. ArrayList<Integer>

B. HashMap

C. Stack<Integer>

D. Queue<Integer>

Solution

1. Step 1: Identify need to map columns to nodes

   We need to group nodes by their vertical column index, so a map from column to list of nodes is needed.

2. Step 2: Choose suitable Java data structure

   A HashMap with key as column index (Integer) and value as list of nodes (List<Integer>) fits perfectly.

3. Final Answer:

   HashMap -> Option B

4. Quick Check:

   Map column to nodes = HashMap [OK]

Hint: Use map from column index to list of nodes [OK]

Common Mistakes:

• Using ArrayList alone without mapping columns
• Using Stack or Queue which don't map keys to lists
• Confusing data structures for traversal order

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

    1
   / \
  2   3
 / \   \
4   5   6

medium

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

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

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

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

Solution

1. Step 1: Assign column indices to nodes

   Root 1 is at column 0. Left child 2 at -1, right child 3 at +1. 4 at -2, 5 at 0, 6 at +2.

2. Step 2: Collect nodes column-wise from left to right

   Columns: -2: [4], -1: [2], 0: [1,5], 1: [3], 2: [6]. Combine: [4, 2, 1, 5, 3, 6]

3. Final Answer:

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

4. Quick Check:

   Columns left to right = [4,2,1,5,3,6] [OK]

Hint: Label columns from root 0, left -1, right +1, then read left to right [OK]

Common Mistakes:

• Ignoring multiple nodes in same column order
• Mixing preorder or inorder output with vertical order
• Not assigning correct column indices

4. Given this Java snippet for vertical order traversal, what is the error?

Map map = new HashMap<>();
Queue> queue = new LinkedList<>();
queue.add(new Pair(root, 0));
while (!queue.isEmpty()) {
  Pair p = queue.poll();
  TreeNode node = p.getKey();
  int col = p.getValue();
  map.putIfAbsent(col, new ArrayList<>());
  map.get(col).add(node.val);
  if (node.left != null) queue.add(new Pair(node.left, col - 1));
  if (node.right != null) queue.add(new Pair(node.right, col + 1));
}

medium

A. Pair class is not imported or defined

B. Queue should be a Stack for correct traversal

C. map.putIfAbsent should be replaced with map.put

D. col should be incremented for left child, not decremented

Solution

1. Step 1: Check usage of Pair class

   The code uses Pair but Java does not have Pair by default; it must be imported or defined.

2. Step 2: Identify missing import or definition

   Without importing javafx.util.Pair or defining a custom Pair class, this code will not compile.

3. Final Answer:

   Pair class is not imported or defined -> Option A

4. Quick Check:

   Missing Pair class causes compile error [OK]

Hint: Check if all classes like Pair are imported or defined [OK]

Common Mistakes:

• Assuming Pair is built-in in Java standard library
• Using Stack instead of Queue for BFS traversal
• Incorrect column increment direction for left child

5. How would you modify vertical order traversal to output nodes sorted by row and then value within each vertical column? Choose the best approach.

hard

A. Use a Queue and print nodes as they are visited

B. Use a HashMap and sort each list after traversal

C. Use a Stack to store nodes and pop in sorted order

D. Use a TreeMap> to map column -> row -> sorted nodes

Solution

1. Step 1: Understand sorting by row and value in vertical columns

   We need to group nodes by column, then by row, and sort nodes with same row by value.

2. Step 2: Choose data structure supporting nested sorting

   TreeMap for columns and rows keeps keys sorted. PriorityQueue stores nodes sorted by value. So TreeMap> fits.

3. Final Answer:

   Use a TreeMap> to map column -> row -> sorted nodes -> Option D

4. Quick Check:

   Nested TreeMaps + PriorityQueue = sorted vertical order [OK]

Hint: Use nested TreeMaps and PriorityQueue for sorted vertical order [OK]

Common Mistakes:

• Sorting lists after traversal loses row info
• Using Stack or Queue which don't sort nodes
• Ignoring row sorting within columns