Vertical Order Traversal of Binary Tree in DSA Go

Mental Model

We group tree nodes by their vertical columns from left to right, and within each column, nodes are ordered top to bottom.

Analogy: Imagine standing in front of a tree and looking straight at it. You draw vertical lines through the tree. Nodes that fall on the same line are grouped together, like people standing in the same vertical queue.

      1
     / \
    2   3
   / \   \
  4   5   6

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

Dry Run Walkthrough

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

Goal: Print nodes grouped by vertical columns from left to right, top to bottom within each column.

Step 1: Start at root node 1 with column 0

Column 0: [1]
Columns so far: {0: [1]}

Why: Root is the center column, so we assign it column 0

Step 2: Move to left child 2 with column -1

Column -1: [2]
Columns so far: {-1: [2], 0: [1]}

Why: Left child is one column to the left

Step 3: Move to left child 4 with column -2

Column -2: [4]
Columns so far: {-2: [4], -1: [2], 0: [1]}

Why: Left child again moves one column left

Step 4: Back to node 2, move to right child 5 with column 0

Column 0: [1,5]
Columns so far: {-2: [4], -1: [2], 0: [1,5]}

Why: Right child moves one column right from parent

Step 5: Back to root 1, move to right child 3 with column 1

Column 1: [3]
Columns so far: {-2: [4], -1: [2], 0: [1,5], 1: [3]}

Why: Right child moves one column right

Step 6: Move to right child 6 of node 3 with column 2

Column 2: [6]
Columns so far: {-2: [4], -1: [2], 0: [1,5], 1: [3], 2: [6]}

Why: Right child moves one column right

Result:

Vertical order traversal:
Column -2: 4
Column -1: 2
Column 0: 1 -> 5
Column 1: 3
Column 2: 6

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func verticalOrderTraversal(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}

	// Map column index to list of node values
	columnTable := make(map[int][]int)
	// Queue for BFS: stores node and its column index
	type pair struct {
		node  *TreeNode
		col int
	}
	queue := []pair{{root, 0}}

	minCol, maxCol := 0, 0

	for len(queue) > 0 {
		p := queue[0]
		queue = queue[1:]

		node, col := p.node, p.col

		columnTable[col] = append(columnTable[col], node.Val) // add node to its column

		if node.Left != nil {
			queue = append(queue, pair{node.Left, col - 1}) // left child column -1
			if col-1 < minCol {
				minCol = col - 1
			}
		}

		if node.Right != nil {
			queue = append(queue, pair{node.Right, col + 1}) // right child column +1
			if col+1 > maxCol {
				maxCol = col + 1
			}
		}
	}

	result := [][]int{}
	for c := minCol; c <= maxCol; c++ {
		result = append(result, columnTable[c]) // collect columns left to right
	}
	return result
}

func main() {
	// Build tree:
	//      1
	//     / \
	//    2   3
	//   / \   \
	//  4   5   6

	n4 := &TreeNode{Val: 4}
	n5 := &TreeNode{Val: 5}
	n6 := &TreeNode{Val: 6}
	n2 := &TreeNode{Val: 2, Left: n4, Right: n5}
	n3 := &TreeNode{Val: 3, Right: n6}
	n1 := &TreeNode{Val: 1, Left: n2, Right: n3}

	res := verticalOrderTraversal(n1)
	for i, col := range res {
		fmt.Printf("Column %d: ", i+minCol)
		for j, val := range col {
			if j > 0 {
				fmt.Print(" -> ")
			}
			fmt.Print(val)
		}
		fmt.Println()
	}
}

queue := []pair{{root, 0}}

Initialize BFS queue with root at column 0

p := queue[0] queue = queue[1:]

Dequeue front node and its column

columnTable[col] = append(columnTable[col], node.Val)

Add current node value to its column group

if node.Left != nil { queue = append(queue, pair{node.Left, col - 1}) if col-1 < minCol { minCol = col - 1 } }

Add left child to queue with column one less, update min column

if node.Right != nil { queue = append(queue, pair{node.Right, col + 1}) if col+1 > maxCol { maxCol = col + 1 } }

Add right child to queue with column one more, update max column

for c := minCol; c <= maxCol; c++ { result = append(result, columnTable[c]) }

Collect columns from leftmost to rightmost

Output

Column -2: 4

Column -1: 2

Column 0: 1 -> 5

Column 1: 3

Column 2: 6

Complexity Analysis

Time: O(n) because we visit each node once during BFS traversal

Space: O(n) for storing nodes in the queue and the column map

vs Alternative: Compared to DFS, BFS naturally processes nodes level by level, preserving top-to-bottom order within columns without extra sorting.

Edge Cases

Empty tree

Returns empty list since there are no nodes

DSA Go

if root == nil {
	return [][]int{}
}

Tree with only root node

Returns list with single column containing root value

DSA Go

queue := []pair{{root, 0}}

Tree with multiple nodes in same column and level

Nodes appear in order they are visited in BFS, preserving top-to-bottom order

DSA Go

columnTable[col] = append(columnTable[col], node.Val)

When to Use This Pattern

When a problem asks to group tree nodes by vertical lines or columns, use vertical order traversal with BFS and column indexing to preserve top-to-bottom order.

Common Mistakes

Mistake: Using DFS without sorting nodes by level causes incorrect top-to-bottom order in columns
Fix: Use BFS traversal to process nodes level by level, ensuring correct vertical order

Mistake: Not tracking min and max column indices leads to unordered output
Fix: Track minCol and maxCol during traversal to output columns from left to right

Summary

Groups binary tree nodes by vertical columns from left to right, preserving top-to-bottom order.

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

The key is to assign column indices during BFS and collect nodes per column in order.