Vertical Order Traversal of Binary Tree in DSA Go - 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 Go

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

func verticalOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    type nodeInfo struct {
        node *TreeNode
        col  int
    }
    queue := []nodeInfo{{root, 0}}
    colTable := map[int][]int{}
    minCol, maxCol := 0, 0
    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]
        colTable[curr.col] = append(colTable[curr.col], curr.node.Val)
        if curr.node.Left != nil {
            queue = append(queue, nodeInfo{curr.node.Left, curr.col - 1})
            if curr.col-1 < minCol {
                minCol = curr.col - 1
            }
        }
        if curr.node.Right != nil {
            queue = append(queue, nodeInfo{curr.node.Right, curr.col + 1})
            if curr.col+1 > maxCol {
                maxCol = curr.col + 1
            }
        }
    }
    result := [][]int{}
    for i := minCol; i <= maxCol; i++ {
        result = append(result, colTable[i])
    }
    return result
}

// Tree structure:
//      1
//     / \
//    2   3
//       / \
//      4   5

root := &TreeNode{1, &TreeNode{2, nil, nil}, &TreeNode{3, &TreeNode{4, nil, nil}, &TreeNode{5, nil, nil}}}
output := verticalOrder(root)
fmt.Println(output)

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

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

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

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

💡 Hint

Think about columns from left to right and nodes in each column by level order.

The vertical order traversal groups nodes by their horizontal distance (column) from the root. The root is at column 0. Left child decreases column by 1, right child increases by 1. Nodes are collected level by level. So column -1 has [2], column 0 has [1,4], column 1 has [3], and column 2 has [5].

🧠 Conceptual

intermediate

Understanding Column Indexing in Vertical Order Traversal

In vertical order traversal, what does the column index represent for each node?

A The depth level of the node in the tree

B The horizontal distance from the root node, with left child decreasing and right child increasing the index

C The order in which nodes are visited during preorder traversal

D The number of nodes in the subtree rooted at that node

💡 Hint

Think about how left and right children affect the position horizontally.

Column index tracks horizontal distance from the root: left child decreases column by 1, right child increases by 1. This helps group nodes vertically.

🔧 Debug

advanced

Identify the Bug in Vertical Order Traversal Code

What error will this Go code produce when running vertical order traversal?

DSA Go

func verticalOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    type nodeInfo struct {
        node *TreeNode
        col  int
    }
    queue := []nodeInfo{{root, 0}}
    colTable := map[int][]int{}
    minCol, maxCol := 0, 0
    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]
        colTable[curr.col] = append(colTable[curr.col], curr.node.Val)
        if curr.node.Left != nil {
            queue = append(queue, nodeInfo{curr.node.Left, curr.col - 1}) // Bug here
            if curr.col-1 < minCol {
                minCol = curr.col - 1
            }
        }
        if curr.node.Right != nil {
            queue = append(queue, nodeInfo{curr.node.Right, curr.col + 1}) // Bug here
            if curr.col+1 > maxCol {
                maxCol = curr.col + 1
            }
        }
    }
    result := [][]int{}
    for i := minCol; i <= maxCol; i++ {
        result = append(result, colTable[i])
    }
    return result
}

A Output will be empty because queue is never updated

B Syntax error due to missing colon in map initialization

C Runtime panic due to nil pointer dereference

D The traversal will produce reversed columns because left and right child column indices are swapped

💡 Hint

Check how column indices are assigned for left and right children.

The code incorrectly increases column index for left child and decreases for right child, reversing the expected horizontal order. This causes columns to be reversed in output.

🚀 Application

advanced

Number of Columns in Vertical Order Traversal

Given the binary tree below, how many columns will the vertical order traversal output contain? // Tree structure: // 10 // / \ // 5 15 // / \ \ // 3 7 18

A 3

B 4

C 5

D 6

💡 Hint

Count columns from leftmost to rightmost node by horizontal distance.

Columns are counted by horizontal distance: 3 is at -2, 5 at -1, 10 at 0, 15 at 1, 18 at 2. So total columns = 5. But 7 is at 0, so columns are from -2 to 2, total 5 columns.

❓ Predict Output

expert

Output of Vertical Order Traversal with Multiple Nodes in Same Column and Level

What is the output of vertical order traversal for the following tree? // Tree structure: // 1 // / \ // 2 3 // / \ / \ // 4 5 6 7 // \ / // 8 9

DSA Go

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

func verticalOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    type nodeInfo struct {
        node *TreeNode
        col  int
    }
    queue := []nodeInfo{{root, 0}}
    colTable := map[int][]int{}
    minCol, maxCol := 0, 0
    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]
        colTable[curr.col] = append(colTable[curr.col], curr.node.Val)
        if curr.node.Left != nil {
            queue = append(queue, nodeInfo{curr.node.Left, curr.col - 1})
            if curr.col-1 < minCol {
                minCol = curr.col - 1
            }
        }
        if curr.node.Right != nil {
            queue = append(queue, nodeInfo{curr.node.Right, curr.col + 1})
            if curr.col+1 > maxCol {
                maxCol = curr.col + 1
            }
        }
    }
    result := [][]int{}
    for i := minCol; i <= maxCol; i++ {
        result = append(result, colTable[i])
    }
    return result
}

root := &TreeNode{1,
    &TreeNode{2,
        &TreeNode{4, nil, nil},
        &TreeNode{5, nil, &TreeNode{8, nil, nil}},
    },
    &TreeNode{3,
        &TreeNode{6, nil, nil},
        &TreeNode{7, &TreeNode{9, nil, nil}, nil},
    },
}
output := verticalOrder(root)
fmt.Println(output)

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

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

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

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

💡 Hint

Remember nodes in the same column are listed by level order (top to bottom, left to right).

Column -2: [4] Column -1: [2] Column 0: [1, 5, 6] (1 at root level, then 5 and 6 at next level) Column 1: [3, 8, 9] (3 at level 1, then 8 and 9 at level 3) Column 2: [7] This matches option A.

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