Vertical Order Traversal of Binary Tree in DSA Java - Build from Scratch

Vertical Order Traversal of Binary Tree

📖 Scenario: Imagine you have a family tree represented as a binary tree. You want to see the family members grouped by their vertical positions when you look at the tree from the side.

🎯 Goal: Build a Java program that performs vertical order traversal on a binary tree. The program will group nodes by their vertical columns and print the nodes in each vertical column from top to bottom.

📋 What You'll Learn

Create a binary tree with the exact structure given

Use a variable to track the root node

Implement vertical order traversal using a breadth-first search approach

Print the nodes grouped by their vertical columns in order from left to right

💡 Why This Matters

🌍 Real World

Vertical order traversal helps visualize hierarchical data like family trees, organizational charts, or layered maps from a side view.

💼 Career

Understanding tree traversals and using data structures like TreeMap and Queue is essential for software engineering roles involving data processing and visualization.

1

Create the Binary Tree

Create a class called TreeNode with int val, TreeNode left, and TreeNode right fields. Then create the binary tree with root node root having value 1, left child 2, right child 3, left child of 2 as 4, and right child of 2 as 5.

DSA Java

// Define TreeNode class and create the binary tree with root
// Your code here

Hint

Define the TreeNode class first. Then create the root and link the children exactly as described.

2

Setup Data Structures for Traversal

Inside the main method, create a TreeMap<Integer, List<Integer>> called columnTable to store nodes by their vertical column index. Also create a Queue<Pair<TreeNode, Integer>> called queue to hold nodes and their column indices for traversal.

DSA Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class VerticalOrderTraversal {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // Create columnTable and queue for traversal
        // Your code here
    }
}

Hint

Use TreeMap to keep columns sorted. Use a Queue of Pair to hold nodes with their column indices.

3

Perform Vertical Order Traversal

Add the root node with column index 0 to queue. Then use a while loop to process nodes from queue. For each node, add its value to the list in columnTable for its column. Add left child with column - 1 and right child with column + 1 to queue if they exist.

DSA Java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class VerticalOrderTraversal {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        TreeMap> columnTable = new TreeMap();
        Queue> queue = new LinkedList();

        // Add root to queue and process nodes
        // Your code here
    }
}

class Pair {
    public K key;
    public V value;
    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

Hint

Start by adding the root with column 0 to the queue. Then loop while queue is not empty, process each node, add its value to the map, and add children with updated columns.

4

Print the Vertical Order Traversal

After the traversal loop, use a for loop to iterate over the columnTable entries. For each column, print the list of node values separated by spaces on one line.

DSA Java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class VerticalOrderTraversal {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        TreeMap> columnTable = new TreeMap();
        Queue> queue = new LinkedList();

        queue.offer(new Pair(root, 0));

        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            TreeNode node = p.key;
            int column = p.value;

            columnTable.putIfAbsent(column, new ArrayList());
            columnTable.get(column).add(node.val);

            if (node.left != null) {
                queue.offer(new Pair(node.left, column - 1));
            }
            if (node.right != null) {
                queue.offer(new Pair(node.right, column + 1));
            }
        }

        // Print the vertical order traversal
        // Your code here
    }
}

class Pair {
    public K key;
    public V value;
    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

Hint

Loop over the values of columnTable. For each list, print all values separated by spaces, then print a new line.

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