Vertical Order Traversal of Binary Tree in DSA Go - Execution Trace

Concept Flow - Vertical Order Traversal of Binary Tree

Start at root node

↓

Assign horizontal distance = 0

↓

Use queue for BFS traversal

↓

Dequeue node

↓

Add node value to map at its horizontal distance

↓

Enqueue left child with hd-1

↓

Enqueue right child with hd+1

↓

Repeat until queue empty

↓

Sort keys of map

↓

Output values in order of sorted keys

Traverse the tree level by level, track horizontal distance (hd) for each node, group nodes by hd, then output groups sorted by hd.

Execution Sample

DSA Go

type Node struct {
  Val int
  Left, Right *Node
}

func VerticalOrder(root *Node) [][]int {
  // BFS with hd tracking
}

This code performs vertical order traversal by BFS, grouping nodes by horizontal distance.

Execution Table

Step	Operation	Node Processed (Val, hd)	Map State (hd: [values])	Queue State (Val, hd)	Visual State
1	Start BFS	Root (1, 0)	{}	[(1,0)]	Tree: 1 / \ 2 3 / \ \ 4 5 6
2	Dequeue node	(1,0)	{0: [1]}	[(2,-1),(3,1)]	Added 1 at hd=0
3	Dequeue node	(2,-1)	{0: [1], -1: [2]}	[(3,1),(4,-2),(5,0)]	Added 2 at hd=-1
4	Dequeue node	(3,1)	{0: [1], -1: [2], 1: [3]}	[(4,-2),(5,0),(6,2)]	Added 3 at hd=1
5	Dequeue node	(4,-2)	{0: [1], -1: [2], 1: [3], -2: [4]}	[(5,0),(6,2)]	Added 4 at hd=-2
6	Dequeue node	(5,0)	{0: [1,5], -1: [2], 1: [3], -2: [4]}	[(6,2)]	Added 5 at hd=0
7	Dequeue node	(6,2)	{0: [1,5], -1: [2], 1: [3], -2: [4], 2: [6]}	[]	Added 6 at hd=2
8	Queue empty	None	{-2: [4], -1: [2], 0: [1,5], 1: [3], 2: [6]}	[]	Traversal complete
9	Sort keys and output	None	Output order: [4], [2], [1,5], [3], [6]	[]	Final vertical order

💡 Queue is empty, all nodes processed

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
Queue	[(1,0)]	[(2,-1),(3,1)]	[(3,1),(4,-2),(5,0)]	[(4,-2),(5,0),(6,2)]	[(5,0),(6,2)]	[(6,2)]	[]	[]
Map	{}	{0: [1]}	{0: [1], -1: [2]}	{0: [1], -1: [2], 1: [3]}	{0: [1], -1: [2], 1: [3], -2: [4]}	{0: [1,5], -1: [2], 1: [3], -2: [4]}	{0: [1,5], -1: [2], 1: [3], -2: [4], 2: [6]}	{-2: [4], -1: [2], 0: [1,5], 1: [3], 2: [6]}

Key Moments - 3 Insights

Why do we assign horizontal distance (hd) starting from 0 at root?

Assigning hd=0 at root gives a reference point. Left child gets hd-1, right child hd+1, so nodes align vertically by hd. See execution_table rows 2-7 where hd changes.

Why do we use a queue for traversal instead of recursion?

Queue ensures level order (BFS) traversal, so nodes are processed top to bottom per vertical line. This keeps vertical order correct. See execution_table queue states from step 2 to 7.

How do we get the final vertical order after traversal?

After BFS, map keys (hd) are sorted from smallest to largest. Values at each hd form one vertical line. See execution_table step 9 for sorted output.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the queue state?

A [(5,0),(6,2)]

B [(4,-2),(5,0),(6,2)]

C [(3,1),(4,-2),(5,0)]

D [(2,-1),(3,1)]

💡 Hint

Check the 'Queue State' column at step 4 in execution_table

At which step does the map first contain the key hd=1?

A Step 5

B Step 3

C Step 4

D Step 6

💡 Hint

Look at 'Map State' column in execution_table rows 3 and 4

If the root had no left child, how would the map change after step 3?

A No entry for hd=-1

B No entry for hd=1

C No entry for hd=0

D Map would be empty

💡 Hint

Left child nodes have hd = parent hd - 1; see variable_tracker and execution_table

Concept Snapshot

Vertical Order Traversal of Binary Tree:
- Assign horizontal distance (hd) 0 to root
- Use BFS with queue to traverse nodes
- For each node, add value to map[hd]
- Left child hd = hd - 1, right child hd = hd + 1
- After traversal, sort map keys
- Output node values grouped by sorted hd

Full Transcript

Vertical Order Traversal visits nodes of a binary tree grouped by their vertical lines. We start at the root with horizontal distance zero. Using a queue, we do a breadth-first search. Each node's value is added to a map keyed by its horizontal distance. Left children get hd one less than parent, right children one more. After processing all nodes, we sort the keys of the map and output the values in that order. This way, nodes are grouped vertically from left to right, and top to bottom within each vertical line.

Practice

1. What does vertical order traversal of a binary tree primarily group nodes by?

easy

A. Their parent node

B. Their depth level in the tree

C. Their value magnitude

D. Their horizontal distance from the root

Solution

1. Step 1: Understand vertical order traversal concept

   Vertical order traversal groups nodes based on their horizontal distance from the root node, also called the vertical column.

2. Step 2: Differentiate from other traversals

   Unlike level order which groups by depth, vertical order groups nodes that align vertically when the tree is viewed from top.

3. Final Answer:

   Their horizontal distance from the root -> Option D

4. Quick Check:

   Vertical order = horizontal distance grouping [OK]

Hint: Remember vertical means grouping by horizontal distance [OK]

Common Mistakes:

• Confusing vertical order with level order traversal
• Grouping by node values instead of position
• Ignoring horizontal distance concept

2. Which Go data structure is best suited to store nodes grouped by their vertical column during vertical order traversal?

easy

A. map[string]int

B. []int

C. map[int][]int

D. [][]int

Solution

1. Step 1: Identify grouping requirement

   We need to group nodes by their vertical column index, which is an integer key.

2. Step 2: Choose suitable Go data structure

   A map with integer keys and slice of integers as values (map[int][]int) allows storing multiple node values per vertical column.

3. Final Answer:

   map[int][]int -> Option C

4. Quick Check:

   Use map[int][]int for vertical groups [OK]

Hint: Use map with int keys and slice values for grouping [OK]

Common Mistakes:

• Using simple slices without keys
• Using map with string keys unnecessarily
• Choosing 2D slices without keys

3. Given the binary tree:

    1
   / \
  2   3
 /     \
4       5

What is the vertical order traversal output?

medium

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

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

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

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

Solution

1. Step 1: Assign horizontal distances

   Root 1 is at 0, left child 2 at -1, left-left 4 at -2, right child 3 at +1, right-right 5 at +2.

2. Step 2: Group nodes by horizontal distance

   At -2: [4], -1: [2], 0: [1], +1: [3], +2: [5].

3. Final Answer:

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

4. Quick Check:

   Group by horizontal distance = [[4], [2], [1], [3, 5]] [OK]

Hint: Label columns from left (-) to right (+) then group nodes [OK]

Common Mistakes:

• Mixing node order inside same vertical column
• Incorrect horizontal distance assignment
• Ignoring multiple nodes in same vertical column

4. Consider this Go snippet for vertical order traversal:

func verticalOrder(root *Node) map[int][]int {
    result := make(map[int][]int)
    var dfs func(node *Node, hd int)
    dfs = func(node *Node, hd int) {
        if node == nil {
            return
        }
        result[hd] = append(result[hd], node.Val)
        dfs(node.Left, hd-1)
        dfs(node.Right, hd+1)
    }
    dfs(root, 0)
    return result
}

What is the main issue with this code?

medium

A. It uses DFS which may not preserve top-to-bottom order

B. It does not handle nil root input

C. It uses map instead of slice for result

D. It increments horizontal distance incorrectly

Solution

1. Step 1: Analyze traversal method

   The code uses DFS which explores depth first, so nodes deeper may be added before shallower nodes in same vertical column.

2. Step 2: Understand vertical order requirement

   Vertical order traversal requires nodes to be output top-to-bottom per vertical column, which BFS preserves but DFS may not.

3. Final Answer:

   It uses DFS which may not preserve top-to-bottom order -> Option A

4. Quick Check:

   DFS can misorder vertical nodes top-to-bottom [OK]

Hint: Use BFS, not DFS, to keep top-to-bottom order [OK]

Common Mistakes:

• Assuming DFS preserves vertical order top-to-bottom
• Ignoring traversal order impact on output
• Thinking map usage causes order issues

5. You want to print the vertical order traversal of a binary tree sorted by vertical column from left to right and nodes top to bottom within each column. Which approach is best?

hard

A. Use BFS with a queue storing nodes and their horizontal distance, then sort keys

B. Use DFS with recursion and store nodes in map without sorting

C. Use inorder traversal and print nodes as visited

D. Use a stack to store nodes and print after traversal

Solution

1. Step 1: Choose traversal preserving top-to-bottom order

   BFS visits nodes level by level, ensuring top nodes are processed before lower nodes in same vertical column.

2. Step 2: Store nodes with horizontal distance and sort keys

   Use a queue to track nodes and their horizontal distance, store in map[int][]int, then output sorted by keys for left to right order.

3. Final Answer:

   Use BFS with a queue storing nodes and their horizontal distance, then sort keys -> Option A

4. Quick Check:

   BFS + sorting keys = correct vertical order traversal [OK]

Hint: BFS + map + sort keys for correct vertical order [OK]

Common Mistakes:

• Using DFS which breaks top-to-bottom order
• Not sorting map keys before printing
• Using stack which reverses order