Vertical Order Traversal of Binary Tree in DSA Java - Deep Dive

Overview - Vertical Order Traversal of Binary Tree

What is it?

Vertical Order Traversal of a Binary Tree is a way to visit all nodes of the tree column by column from left to right. Each column contains nodes that share the same horizontal distance from the root. We list nodes top to bottom within each column. This helps us see the tree as if looking from the side, grouping nodes vertically.

Why it matters

Without vertical order traversal, we cannot easily group nodes that align vertically in a tree. This grouping is useful in many applications like printing trees in a human-friendly way, solving problems related to views of trees, and understanding spatial relationships in hierarchical data. Without it, we lose a natural way to visualize and process tree data from a vertical perspective.

Where it fits

Before learning this, you should understand basic binary trees and tree traversals like preorder, inorder, and level order. After mastering vertical order traversal, you can explore related concepts like top view, bottom view of trees, and horizontal distance based tree problems.

Mental Model

Core Idea

Vertical order traversal groups tree nodes by their horizontal distance from the root and lists them top to bottom within each group.

Think of it like...

Imagine standing in front of a tall bookshelf and looking straight at it. Each vertical shelf column holds books stacked from top to bottom. Vertical order traversal is like reading the books column by column from left to right.

          (root)
            1
          /   \
         2     3
        / \   / \
       4   5 6   7

Horizontal distances:
Node 4: -2 | Node 2: -1 | Node 1: 0 | Node 3: 1 | Node 7: 2
Vertical columns:
-2: [4]
-1: [2]
 0: [1,5,6]
 1: [3]
 2: [7]

Build-Up - 7 Steps

1

Foundation

Understanding Binary Tree Structure

Concept: Learn what a binary tree is and how nodes connect with left and right children.

A binary tree is a structure where each node has up to two children: left and right. The top node is called the root. Nodes below connect downwards. For example, node 1 can have node 2 as left child and node 3 as right child.

Result

You can visualize and represent a binary tree with nodes and their left/right links.

Understanding the tree structure is essential because vertical order traversal depends on node positions relative to the root.

2

Foundation

Horizontal Distance Concept

Concept: Introduce horizontal distance (HD) as a way to measure node position relative to root horizontally.

Assign the root node a horizontal distance of 0. For any node, its left child has HD = parent's HD - 1, and right child has HD = parent's HD + 1. This helps group nodes vertically by their HD.

Result

Each node now has a number representing its vertical column position.

Horizontal distance is the key to grouping nodes vertically, enabling vertical order traversal.

3

Intermediate

Level Order Traversal with HD Tracking

🤔Before reading on: Do you think we can use simple preorder traversal to get vertical order? Commit to yes or no.

Concept: Use a breadth-first search (level order) to visit nodes while tracking their horizontal distances.

We use a queue to visit nodes level by level. Along with each node, we store its HD. When we visit a node, we add its value to a map keyed by HD. Then enqueue its children with updated HDs.

Result

We get a map from HD to list of nodes in top-to-bottom order for that vertical column.

Level order traversal ensures nodes are processed top to bottom, which is crucial for correct vertical order output.

4

Intermediate

Sorting and Output Formatting

🤔Before reading on: Should vertical columns be output in ascending or descending HD order? Commit to your answer.

Concept: After collecting nodes by HD, sort the keys (HDs) in ascending order to output columns from left to right.

Once traversal is done, we iterate over the sorted HD keys and print the list of nodes for each HD. This gives the vertical order traversal output.

Result

Nodes are printed column by column from leftmost to rightmost vertical line.

Sorting HD keys ensures the output matches the natural left-to-right vertical order.

5

Intermediate

Handling Nodes at Same Position

🤔Before reading on: If two nodes share the same HD and level, should their order be based on insertion or value? Commit your guess.

Concept: When nodes share the same HD and level, order them by their appearance in level order traversal (top to bottom, left to right).

Because we use level order traversal, nodes at the same level and HD are visited in left to right order naturally. This preserves the correct order in the output list.

Result

Nodes at the same vertical and horizontal level appear in the correct order.

Using level order traversal naturally resolves ordering conflicts without extra sorting.

6

Advanced

Java Implementation with TreeMap and Queue

🤔Before reading on: Do you think a HashMap or TreeMap is better for storing HD keys? Commit your answer.

Concept: Use a TreeMap to keep HD keys sorted automatically and a Queue for BFS traversal.

Code snippet: import java.util.*; class Node { int val; Node left, right; Node(int v) { val = v; } } public class VerticalOrder { public static List> verticalOrder(Node root) { List> result = new ArrayList<>(); if (root == null) return result; TreeMap> map = new TreeMap<>(); Queue> queue = new LinkedList<>(); queue.offer(new Pair<>(root, 0)); while (!queue.isEmpty()) { Pair p = queue.poll(); Node node = p.getKey(); int hd = p.getValue(); map.computeIfAbsent(hd, k -> new ArrayList<>()).add(node.val); if (node.left != null) queue.offer(new Pair<>(node.left, hd - 1)); if (node.right != null) queue.offer(new Pair<>(node.right, hd + 1)); } for (List col : map.values()) { result.add(col); } return result; } } Output for tree with root 1, left 2, right 3, etc., matches vertical order.

Result

The method returns a list of lists, each inner list representing a vertical column from left to right.

Using TreeMap and Queue together simplifies sorting and traversal, making the implementation clean and efficient.

7

Expert

Handling Complex Cases and Optimizations

🤔Before reading on: Can vertical order traversal be done without extra space for maps? Commit yes or no.

Concept: Discuss edge cases like multiple nodes at same HD and level, and explore space/time tradeoffs and possible optimizations.

In some cases, nodes share HD and level; to order them by value, extra sorting is needed. Also, vertical order traversal requires O(n) space for maps and queues. Optimizations include using custom data structures or combining traversal with other tree operations. Doing it without extra space is generally not possible because we must remember nodes by HD.

Result

Understanding these nuances helps write robust code and optimize performance in large trees.

Knowing the limits and tradeoffs of vertical order traversal prepares you for real-world challenges and advanced tree problems.

Under the Hood

Vertical order traversal works by assigning each node a horizontal distance (HD) from the root. The root is 0, left child is HD-1, right child is HD+1. Using a breadth-first search (level order), nodes are visited top to bottom. A map stores nodes grouped by HD. After traversal, the map keys are sorted to output nodes column by column. This approach ensures correct vertical grouping and top-to-bottom order.

Why designed this way?

This method was designed to combine horizontal positioning (HD) with vertical ordering (level order) to solve the problem of grouping nodes vertically while preserving top-down order. Alternatives like preorder or inorder traversals do not guarantee top-to-bottom order within columns. Using a TreeMap keeps keys sorted automatically, simplifying output. The design balances clarity, correctness, and efficiency.

┌─────────────┐
│   Root (HD=0)│
└─────┬───────┘
      │
 ┌────┴─────┐
 │          │
Left       Right
(HD-1)     (HD+1)

Traversal Queue:
[Node, HD]

Map:
HD -> List of Nodes

After BFS:
-2: [4]
-1: [2]
 0: [1,5,6]
 1: [3]
 2: [7]

Myth Busters - 3 Common Misconceptions

Quick: Does preorder traversal alone produce correct vertical order? Commit yes or no.

Common Belief: Preorder traversal can be used directly to get vertical order traversal.

Reality: Preorder traversal does not guarantee nodes are processed top to bottom within vertical columns, so it cannot produce correct vertical order alone.

Why it matters: Using preorder leads to incorrect vertical order output, mixing node order and confusing the vertical grouping.

Quick: If two nodes share the same HD and level, can their order be arbitrary? Commit yes or no.

Common Belief: Order of nodes at the same HD and level does not matter in vertical order traversal.

Reality: Order matters and should follow left to right appearance in the tree, which level order traversal naturally preserves.

Why it matters: Ignoring order causes inconsistent outputs and breaks assumptions in problems relying on vertical order traversal.

Quick: Can vertical order traversal be done without extra space for maps or queues? Commit yes or no.

Common Belief: Vertical order traversal can be done in-place without extra data structures.

Reality: It requires extra space to store nodes by HD and to perform level order traversal, so in-place is not feasible.

Why it matters: Trying to do it in-place leads to incomplete or incorrect traversal results.

Expert Zone

1

When nodes share the same HD and level, some problems require sorting by node value, which needs extra sorting beyond level order traversal.

2

Using a TreeMap ensures HD keys are sorted, but it adds overhead; in performance-critical cases, a balanced BST or array offset can be used instead.

3

In very large trees, memory usage for storing all nodes by HD can be significant; streaming or partial traversal techniques may be needed.

When NOT to use

Vertical order traversal is not suitable when only top or bottom views of the tree are needed; specialized algorithms for top or bottom view are more efficient. Also, for trees without clear horizontal distance meaning (e.g., non-binary trees), this method does not apply.

Production Patterns

Used in graphical tree visualizations, spatial indexing, and problems requiring grouping nodes by vertical alignment. Also common in coding interviews to test understanding of BFS, maps, and tree traversal combinations.

Connections

Breadth-First Search (BFS)

Vertical order traversal builds on BFS by adding horizontal distance tracking.

Understanding BFS helps grasp why nodes are processed top to bottom, which is essential for correct vertical order.

Top View of Binary Tree

Top view is a special case of vertical order traversal showing only the first node in each vertical column.

Knowing vertical order traversal clarifies how top view is extracted by selecting the first node per column.

Geographical Mapping and Coordinates

Horizontal distance in trees is analogous to x-coordinates in mapping, grouping points vertically.

This connection shows how spatial grouping concepts in geography relate to tree traversal, enriching understanding of coordinate systems.

Common Pitfalls

#1 Using preorder traversal instead of level order for vertical grouping.

Wrong approach:

void preorder(Node node, int hd, Map> map) {
if (node == null) return;
map.computeIfAbsent(hd, k -> new ArrayList<>()).add(node.val);
preorder(node.left, hd - 1, map);
preorder(node.right, hd + 1, map);
}

Correct approach:

Use a queue for level order traversal with HD tracking:
Queue> queue = new LinkedList<>();
queue.offer(new Pair<>(root, 0));
while (!queue.isEmpty()) {
Pair p = queue.poll();
// process node
// enqueue children with updated HD
}

Root cause:

Misunderstanding that preorder does not preserve top-to-bottom order within vertical columns.

#2 Not sorting the horizontal distance keys before output.

Wrong approach:

for (Integer hd : map.keySet()) {
print(map.get(hd));
}

Correct approach:

Use a TreeMap or sort keys:
for (Integer hd : new TreeSet<>(map.keySet())) {
print(map.get(hd));
}

Root cause:

Assuming map keys are ordered by default, which is false for HashMap.

#3 Ignoring order of nodes at same HD and level, leading to inconsistent output.

Wrong approach:

Collect nodes in any order without level order traversal, e.g., DFS only.

Correct approach:

Use level order traversal to ensure nodes at same HD and level are processed left to right.

Root cause:

Not recognizing the importance of traversal order for node ordering in vertical columns.

Key Takeaways

Vertical order traversal groups nodes by horizontal distance from the root and lists them top to bottom within each group.

Using level order traversal with horizontal distance tracking ensures correct top-to-bottom order in each vertical column.

A TreeMap or sorted keys are necessary to output vertical columns from left to right.

Preorder or inorder traversals alone cannot produce correct vertical order because they do not preserve vertical top-down order.

Handling nodes at the same horizontal distance and level requires careful traversal order to maintain consistent output.

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