Vertical Order Traversal of Binary Tree in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare a struct for a binary tree node.

DSA Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *[1]
}

Drag options to blanks, or click blank then click option'

Astring

BTreeNode

Cint

DNode

Attempts:

3 left

💡 Hint

Common Mistakes

Using int or string instead of *TreeNode for child pointers.

Forgetting the pointer symbol * before TreeNode.

The Right child of a binary tree node is a pointer to another TreeNode struct.

2fill in blank

medium

Complete the code to initialize a map that stores vertical order nodes by their horizontal distance.

DSA Go

verticalMap := make(map[int][]int)

// Add root value at horizontal distance 0
verticalMap[[1]] = append(verticalMap[0], root.Val)

Drag options to blanks, or click blank then click option'

A0

B-1

C1

Droot.Val

Attempts:

3 left

💡 Hint

Common Mistakes

Using root.Val as the key instead of 0.

Using 1 or -1 which represent child nodes, not root.

The root node is at horizontal distance 0, so we use 0 as the key in the map.

3fill in blank

hard

Fix the error in the recursive call to traverse the left subtree with updated horizontal distance.

DSA Go

func traverse(node *TreeNode, hd int, verticalMap map[int][]int) {
    if node == nil {
        return
    }
    verticalMap[hd] = append(verticalMap[hd], node.Val)
    traverse(node.Left, hd [1] 1, verticalMap)
    traverse(node.Right, hd + 1, verticalMap)
}

Drag options to blanks, or click blank then click option'

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' instead of '-' for left child horizontal distance.

Using multiplication or division operators which are incorrect here.

For the left child, horizontal distance decreases by 1, so use hd - 1.

4fill in blank

hard

Fill both blanks to sort the keys of the verticalMap and collect values in order.

DSA Go

var keys []int
for k := range verticalMap {
    keys = append(keys, [1])
}
sort.[2](keys)

var result [][]int
for _, k := range keys {
    result = append(result, verticalMap[k])
}

Drag options to blanks, or click blank then click option'

Ak

Bkeys

CInts

DSort

Attempts:

3 left

💡 Hint

Common Mistakes

Appending keys instead of k in the loop.

Using sort.Sort or sort.Sort(keys) which requires a different type.

Using capitalized Sort instead of Ints.

We append each key k to keys slice, then sort keys using sort.Ints to get ascending order.

5fill in blank

hard

Fill all three blanks to complete the vertical order traversal function returning the result.

DSA Go

func verticalOrder(root *TreeNode) [][]int {
    verticalMap := make(map[int][]int)
    traverse(root, 0, verticalMap)

    var keys []int
    for k := range verticalMap {
        keys = append(keys, [1])
    }
    sort.[2](keys)

    var result [][]int
    for _, k := range keys {
        result = append(result, verticalMap[[3]])
    }
    return result
}

Drag options to blanks, or click blank then click option'

Ak

BInts

DSort

Attempts:

3 left

💡 Hint

Common Mistakes

Using Sort instead of Ints for sorting.

Using wrong variable names instead of k.

Forgetting to return the result slice.

We append each key k, sort keys with sort.Ints, and append verticalMap[k] to result.