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

DSA Python

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

def vertical_order(root):
    from collections import defaultdict, deque
    if not root:
        return []
    column_table = defaultdict(list)
    queue = deque([(root, 0)])
    while queue:
        node, column = queue.popleft()
        if node is not None:
            column_table[column].append(node.val)
            queue.append((node.left, column - 1))
            queue.append((node.right, column + 1))
    return [column_table[x] for x in sorted(column_table)]

# Tree construction
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)

print(vertical_order(root))

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

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

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

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

💡 Hint

Think about how nodes are grouped by their horizontal distance from the root.

Nodes are grouped by their vertical columns. Column -2 has [4], -1 has [2], 0 has [1,5,6], 1 has [3], and 2 has [7].

❓ Predict Output

intermediate

Output for Vertical Order Traversal with Overlapping Nodes

What is the output of vertical order traversal for this binary tree with overlapping nodes in the same vertical column?

DSA Python

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

def vertical_order(root):
    from collections import defaultdict, deque
    if not root:
        return []
    column_table = defaultdict(list)
    queue = deque([(root, 0)])
    while queue:
        node, column = queue.popleft()
        if node is not None:
            column_table[column].append(node.val)
            queue.append((node.left, column - 1))
            queue.append((node.right, column + 1))
    return [column_table[x] for x in sorted(column_table)]

# Tree construction
root = Node(3)
root.left = Node(9)
root.right = Node(8)
root.left.right = Node(4)
root.right.left = Node(1)
root.right.right = Node(7)

print(vertical_order(root))

A [[9], [3], [4, 8, 1], [7]]

B [[9], [3, 4, 1], [8], [7]]

C [[9], [3, 4], [8, 1], [7]]

D [[9, 4], [3, 1], [8, 7]]

💡 Hint

Remember nodes are grouped by their vertical column and visited level by level.

The vertical columns are: -1: [9], 0: [3,4,1], 1: [8], 2: [7].

🧠 Conceptual

advanced

Understanding Vertical Order Traversal Data Structure

Which data structure is most suitable to store nodes during vertical order traversal to maintain the order of nodes at the same vertical and horizontal level?

A Stack

B HashSet

C Queue

D Priority Queue

💡 Hint

Think about the order nodes are visited in a level-wise traversal.

A queue is used for breadth-first traversal to process nodes level by level, preserving the order of nodes at the same vertical and horizontal level.

❓ Predict Output

advanced

Output of Vertical Order Traversal with Negative and Positive Columns

What is the output of vertical order traversal for the following binary tree?

DSA Python

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

def vertical_order(root):
    from collections import defaultdict, deque
    if not root:
        return []
    column_table = defaultdict(list)
    queue = deque([(root, 0)])
    while queue:
        node, column = queue.popleft()
        if node is not None:
            column_table[column].append(node.val)
            queue.append((node.left, column - 1))
            queue.append((node.right, column + 1))
    return [column_table[x] for x in sorted(column_table)]

# Tree construction
root = Node(10)
root.left = Node(20)
root.right = Node(30)
root.left.left = Node(40)
root.left.right = Node(50)
root.right.right = Node(60)

print(vertical_order(root))

A [[40], [20], [10, 50], [30], [60]]

B [[40], [20, 50], [10], [30, 60]]

C [[40, 20], [10, 50], [30, 60]]

D [[10], [20, 40, 50], [30, 60]]

💡 Hint

Check how the horizontal distance changes with left and right children.

Columns are: -2: [40], -1: [20], 0: [10, 50], 1: [30], 2: [60].

🔧 Debug

expert

Identify the Error in Vertical Order Traversal Implementation

What error will the following vertical order traversal code produce when run on a non-empty binary tree?

DSA Python

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

def vertical_order(root):
    from collections import defaultdict
    if not root:
        return []
    column_table = defaultdict(list)
    queue = [(root, 0)]
    while queue:
        node, column = queue.pop()
        if node is not None:
            column_table[column].append(node.val)
            queue.append((node.left, column - 1))
            queue.append((node.right, column + 1))
    return [column_table[x] for x in sorted(column_table)]

A The code raises a TypeError due to wrong data structure usage.

B The code runs correctly and returns the vertical order traversal.

C The code raises a KeyError when accessing column_table.

D The code raises an infinite loop because nodes are added but popped from the end.

💡 Hint

Consider how the queue is used and how nodes are popped.

Using list as a stack (pop from end) causes depth-first traversal, adding nodes repeatedly without proper level order, leading to infinite loop.

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