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

Vertical Order Traversal of Binary Tree

📖 Scenario: You are working on a program that helps visualize a family tree. You want to print the family members in vertical order, from left to right, based on their position in the tree.

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

📋 What You'll Learn

Create a binary tree with exact nodes and structure

Use a map to group nodes by their vertical column index

Traverse the tree using a queue and track horizontal distances

Print the nodes in vertical order from leftmost to rightmost column

💡 Why This Matters

🌍 Real World

Vertical order traversal helps in visualizing hierarchical data like family trees, organizational charts, or layered maps.

💼 Career

Understanding tree traversals and grouping data by position is important for roles in software development, data analysis, and system design.

1

Create the Binary Tree

Create a binary tree with the exact structure: root node with value 1, left child 2, right child 3, left child of 2 is 4, right child of 2 is 5, right child of 3 is 6.

DSA Go

// Define the TreeNode struct and create the binary tree nodes
// Your code here

Hint

Define a struct TreeNode with Val, Left, and Right fields. Then create nodes and link them exactly as described.

2

Setup Map and Queue for Traversal

Create a map called columnTable to group nodes by their column index (int to slice of ints). Create a queue slice of pairs where each pair holds a *TreeNode and its column index as int. Initialize the queue with the root node and column index 0.

DSA Go

package main

import "fmt"

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

type Pair struct {
    Node  *TreeNode
    Col   int
}

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 5}
    root.Right.Right = &TreeNode{Val: 6}

    // Create columnTable map and queue slice
    // Your code here
}

Hint

Use make(map[int][]int) to create the map. Define a Pair struct to hold node and column index. Initialize queue with root and column 0.

3

Perform Vertical Order Traversal

Use a for loop to process nodes in queue until empty. For each Pair, append the node's value to columnTable at the node's column. If the node has a left child, enqueue it with column - 1. If the node has a right child, enqueue it with column + 1.

DSA Go

package main

import "fmt"

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

type Pair struct {
    Node  *TreeNode
    Col   int
}

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 5}
    root.Right.Right = &TreeNode{Val: 6}

    columnTable := make(map[int][]int)
    queue := []Pair{{Node: root, Col: 0}}

    // Use a for loop to process queue until empty
    // Your code here
}

Hint

Use a loop to dequeue from queue. Append node values to columnTable. Enqueue children with updated column indices.

4

Print Vertical Order Traversal Result

Find the minimum and maximum column indices in columnTable. Use a for loop from minimum to maximum column index to print the nodes in each column as a slice.

DSA Go

package main

import "fmt"

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

type Pair struct {
    Node  *TreeNode
    Col   int
}

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 5}
    root.Right.Right = &TreeNode{Val: 6}

    columnTable := make(map[int][]int)
    queue := []Pair{{Node: root, Col: 0}}

    for len(queue) > 0 {
        pair := queue[0]
        queue = queue[1:]
        node := pair.Node
        col := pair.Col

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

        if node.Left != nil {
            queue = append(queue, Pair{Node: node.Left, Col: col - 1})
        }
        if node.Right != nil {
            queue = append(queue, Pair{Node: node.Right, Col: col + 1})
        }
    }

    // Print nodes in vertical order from min to max column
    // Your code here
}

Hint

Find min and max keys in columnTable. Loop from min to max and print the slices stored at each key.