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.