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

Vertical Order Traversal of Binary Tree

📖 Scenario: You are working on a program that processes a binary tree representing a company's organizational chart. You want to list employees in vertical order from left to right, grouping employees who are vertically aligned.

🎯 Goal: Build a program that performs vertical order traversal of a binary tree and prints the nodes grouped by their vertical columns from left to right.

📋 What You'll Learn

Create a binary tree with the exact structure given

Use a variable to track the horizontal distance of nodes

Implement vertical order traversal using a queue and dictionary

Print the nodes grouped by their vertical columns in order

💡 Why This Matters

🌍 Real World

Vertical order traversal is useful in graphical applications, like rendering trees or organizational charts, where nodes aligned vertically need to be grouped and displayed together.

💼 Career

Understanding tree traversals and how to group nodes by position is important for software engineers working with hierarchical data, UI rendering, and complex data structures.

1

Create the Binary Tree

Create the exact binary tree by defining a class Node with attributes val, left, and right. Then create nodes with values 1, 2, 3, 4, 5, 6, and 7 and link them to form this tree:

1
/ \
2 3
/ \ / \
4 5 6 7

DSA Python

# Define the Node class and create the tree nodes
# Your code here

Hint

Define a simple Node class with val, left, and right attributes. Then create each node and connect them as shown.

2

Set Up Data Structures for Traversal

Create a dictionary called column_table to store nodes by their vertical column index. Also create a queue called queue and add a tuple with the root node and its column index 0.

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

# Create column_table dictionary and queue with root and column 0
# Your code here

Hint

Use collections.deque for the queue. Initialize column_table as an empty dictionary.

3

Perform Vertical Order Traversal

Use a while loop to process nodes in queue. For each node and its column index, add the node's value to column_table under the column key. If the node has a left child, add it to queue with column index minus one. If the node has a right child, add it to queue with column index plus one.

DSA Python

from collections import deque

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

column_table = {}
queue = deque([(root, 0)])

# Traverse the tree vertically and fill column_table
# Your code here

Hint

Use a breadth-first search approach with a queue. Track each node's column index and add values to column_table.

4

Print Vertical Order Traversal Result

Print the nodes grouped by their vertical columns in order from the smallest column index to the largest. Use sorted(column_table.keys()) to get the columns in order and print the list of node values for each column.

DSA Python

from collections import deque

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

column_table = {}
queue = deque([(root, 0)])

while queue:
    node, column = queue.popleft()
    if column in column_table:
        column_table[column].append(node.val)
    else:
        column_table[column] = [node.val]
    if node.left:
        queue.append((node.left, column - 1))
    if node.right:
        queue.append((node.right, column + 1))

# Print the vertical order traversal
# Your code here

Hint

Sort the keys of column_table and print the list of node values for each column.

Practice

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

easy

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

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

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

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

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

   It means collecting nodes column-wise from leftmost to rightmost column.

3. Final Answer:

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

4. Quick Check:

   Vertical order = group nodes by columns [OK]

Hint: Think columns from left to right for vertical order [OK]

Common Mistakes:

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

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

easy

A. Dictionary with column as key and list of nodes as value

B. List

C. Set

D. Tuple

Solution

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

   We need to map each column number to the nodes in that column.

2. Step 2: Choose data structure for mapping

   A dictionary with column keys and list values is ideal for grouping nodes by column.

3. Final Answer:

   Dictionary with column as key and list of nodes as value -> Option A

4. Quick Check:

   Use dict for column to nodes mapping [OK]

Hint: Use dict to map columns to node lists [OK]

Common Mistakes:

• Using list only without mapping columns
• Using set which loses order
• Using tuple which is immutable

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

    1
   / \
  2   3
 / \   \
4   5   6

medium

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

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

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

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

Solution

1. Step 1: Assign column indices to nodes

   Root 1 is column 0; left child 2 is -1; right child 3 is +1; 4 is -2; 5 is 0; 6 is +2.

2. Step 2: Group nodes by columns and order top to bottom

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

3. Final Answer:

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

4. Quick Check:

   Group nodes by column indices [OK]

Hint: Assign columns: left -1, right +1 from root [OK]

Common Mistakes:

• Mixing node order within same column
• Ignoring column indices for children
• Grouping nodes by rows instead of columns

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

def vertical_order(root):
    if not root:
        return []
    col_table = {}
    queue = [(root, 0)]
    while queue:
        node, col = queue.pop()
        if col not in col_table:
            col_table[col] = []
        col_table[col].append(node.val)
        if node.left:
            queue.append((node.left, col - 1))
        if node.right:
            queue.append((node.right, col + 1))
    return [col_table[x] for x in sorted(col_table)]

medium

A. Using pop() removes last element, should use pop(0) for BFS

B. Dictionary keys should be strings, not integers

C. Appending node values instead of nodes causes error

D. Missing check for empty tree at start

Solution

1. Step 1: Analyze queue usage for BFS

   Queue should remove elements from front (pop(0)) for BFS, but pop() removes from end (LIFO).

2. Step 2: Identify impact on traversal order

   Using pop() causes DFS-like order, breaking vertical order traversal logic.

3. Final Answer:

   Using pop() removes last element, should use pop(0) for BFS -> Option A

4. Quick Check:

   Use pop(0) for BFS queue [OK]

Hint: Use pop(0) to dequeue for BFS, not pop() [OK]

Common Mistakes:

• Using pop() instead of pop(0) in BFS queue
• Confusing BFS with DFS traversal order
• Not sorting dictionary keys before output

5. Given a binary tree where multiple nodes share the same vertical and horizontal distance, how should vertical order traversal output be ordered?

hard

A. Sort nodes by column only, ignoring row and value

B. Sort nodes by value only, ignoring position

C. Output nodes in insertion order without sorting

D. Sort nodes by their row (top to bottom), then by value ascending if tie

Solution

1. Step 1: Understand tie cases in vertical order

   When nodes share same column and row, order by node value ascending to maintain consistency.

2. Step 2: Define final ordering rule

   Sort nodes first by row (top to bottom), then by value ascending if rows tie.

3. Final Answer:

   Sort nodes by their row (top to bottom), then by value ascending if tie -> Option D

4. Quick Check:

   Row then value sorting for ties [OK]

Hint: Sort by row, then value for nodes sharing position [OK]

Common Mistakes:

• Ignoring row order and sorting only by column
• Not sorting nodes with same position by value
• Outputting nodes in random or insertion order