Vertical Order Traversal of Binary Tree in DSA Python

Mental Model

We group tree nodes by their vertical columns from left to right, and list nodes top to bottom in each column.

Analogy: Imagine standing in front of a tree and looking straight at it. Nodes that line up vertically form a column. We write down nodes column by column from left to right, and within each column from top to bottom.

      1
     / \
    2   3
   / \   \
  4   5   6

Columns:  -2  -1   0    1    2
Nodes:   4, 2, 1, 5, 3, 6

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 / \ \ 4 5 6

Goal: List nodes vertically column by column from left to right, top to bottom in each column.

Step 1: Start at root node 1 with column 0 and row 0

Queue: [(1, col=0, row=0)]
Columns map: {}

Why: We begin traversal from root at center column 0

Step 2: Pop node 1, add value 1 to column 0 at row 0

Columns map: {0: [(0,1)]}
Queue: [(2, col=-1, row=1), (3, col=1, row=1)]

Why: Node 1 is at column 0, row 0; add children with updated columns and rows

Step 3: Pop node 2, add value 2 to column -1 at row 1

Columns map: {0: [(0,1)], -1: [(1,2)]}
Queue: [(3, col=1, row=1), (4, col=-2, row=2), (5, col=0, row=2)]

Why: Node 2 is left child, column decreases by 1, row increases by 1

Step 4: Pop node 3, add value 3 to column 1 at row 1

Columns map: {0: [(0,1)], -1: [(1,2)], 1: [(1,3)]}
Queue: [(4, col=-2, row=2), (5, col=0, row=2), (6, col=2, row=2)]

Why: Node 3 is right child, column increases by 1, row increases by 1

Step 5: Pop node 4, add value 4 to column -2 at row 2

Columns map: {0: [(0,1)], -1: [(1,2)], 1: [(1,3)], -2: [(2,4)]}
Queue: [(5, col=0, row=2), (6, col=2, row=2)]

Why: Node 4 is left child of 2, column decreases by 1 again

Step 6: Pop node 5, add value 5 to column 0 at row 2

Columns map: {0: [(0,1),(2,5)], -1: [(1,2)], 1: [(1,3)], -2: [(2,4)]}
Queue: [(6, col=2, row=2)]

Why: Node 5 is right child of 2, column back to 0

Step 7: Pop node 6, add value 6 to column 2 at row 2

Columns map: {0: [(0,1),(2,5)], -1: [(1,2)], 1: [(1,3)], -2: [(2,4)], 2: [(2,6)]}
Queue: []

Why: Node 6 is right child of 3, column increases by 1 again

Step 8: Sort nodes in each column by row and extract values

Final vertical order: [[4], [2], [1,5], [3], [6]]

Why: Sorting by row ensures top to bottom order in each vertical column

Result:

Columns from left to right:
-2: 4
-1: 2
 0: 1 -> 5
 1: 3
 2: 6
Output: [[4], [2], [1,5], [3], [6]]

Annotated Code

DSA Python

from collections import defaultdict, deque

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

def vertical_order_traversal(root):
    if not root:
        return []
    columns = defaultdict(list)  # map col -> list of (row, val)
    queue = deque([(root, 0, 0)])  # node, col, row

    while queue:
        node, col, row = queue.popleft()
        columns[col].append((row, node.val))  # add node to its column

        if node.left:
            queue.append((node.left, col - 1, row + 1))  # left child col-1, row+1
        if node.right:
            queue.append((node.right, col + 1, row + 1))  # right child col+1, row+1

    # sort columns by col index
    sorted_cols = sorted(columns.items())

    result = []
    for col, nodes in sorted_cols:
        # sort nodes by row then value
        nodes.sort(key=lambda x: (x[0], x[1]))
        col_vals = [val for row, val in nodes]
        result.append(col_vals)
    return result

# Driver code to test
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

output = vertical_order_traversal(root)
print(output)

queue = deque([(root, 0, 0)])

Initialize queue with root at column 0, row 0

node, col, row = queue.popleft()

Pop next node with its column and row

columns[col].append((row, node.val))

Add node value to its column with row info

if node.left: queue.append((node.left, col - 1, row + 1))

Add left child with column one less and row one more

if node.right: queue.append((node.right, col + 1, row + 1))

Add right child with column one more and row one more

sorted_cols = sorted(columns.items())

Sort columns by their column index from left to right

nodes.sort(key=lambda x: (x[0], x[1]))

Sort nodes in each column by row then value for top to bottom order

result.append(col_vals)

Collect sorted node values for each column

Output

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

Complexity Analysis

Time: O(n log n) because we visit each of the n nodes once and then sort nodes in each column by row and value

Space: O(n) because we store all nodes in the columns map and queue

vs Alternative: Compared to naive DFS without column tracking, BFS with column and row tracking ensures correct vertical and top-to-bottom order but requires sorting which adds log n factor

Edge Cases

Empty tree (root is None)

Returns empty list immediately

DSA Python

if not root:
    return []

Tree with only root node

Returns list with single column containing root value

DSA Python

queue = deque([(root, 0, 0)])

Multiple nodes in same column and row

Nodes sorted by value to maintain consistent order

DSA Python

nodes.sort(key=lambda x: (x[0], x[1]))

When to Use This Pattern

When a problem asks to print or return nodes of a binary tree grouped by vertical columns from left to right, use vertical order traversal with BFS and column tracking to maintain order.

Common Mistakes

Mistake: Not tracking row number, causing incorrect top-to-bottom order in columns
Fix: Track row along with column during BFS and sort nodes by row before output

Mistake: Using DFS without sorting, leading to wrong vertical order
Fix: Use BFS with queue to process nodes level by level and sort nodes in each column by row

Summary

Groups binary tree nodes by vertical columns from left to right, top to bottom in each column.

Use when you need to print or return nodes column-wise vertically in a binary tree.

Track column and row for each node during BFS, then sort nodes in each column by row to get correct vertical order.

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