Bottom View of Binary Tree in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

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

DSA Go

type Node struct {
	data int
	left *Node
	[1] *Node
}

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

Achild

Bnext

Cparent

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'child' or 'next' instead of 'right' for the right child pointer.

The right child pointer in a binary tree node is named 'right'.

2fill in blank

medium

Complete the code to initialize the horizontal distance map for bottom view.

DSA Go

hdMap := make(map[int]int) // map of horizontal distance to [1]

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

Anode pointers

Bnode count

Cnode data

Dnode depth

Attempts:

3 left

💡 Hint

Common Mistakes

Storing node pointers instead of node data in the map.

The map stores the data of the bottom-most node at each horizontal distance.

3fill in blank

hard

Fix the error in the BFS traversal to update horizontal distance and level.

DSA Go

queue = append(queue, struct{node *Node; hd, lvl int}{root, 0, 0})
for len(queue) > 0 {
	curr := queue[0]
	queue = queue[1:]
	if curr.lvl >= levelMap[curr.hd] {
		levelMap[curr.hd] = curr.lvl
		hdMap[curr.hd] = curr.node.data
	}
	if curr.node.left != nil {
		queue = append(queue, struct{node *Node; hd, lvl int}{curr.node.left, curr.hd [1] 1, curr.lvl [2] 1})
	}
	if curr.node.right != nil {
		queue = append(queue, struct{node *Node; hd, lvl int}{curr.node.right, curr.hd [1] 1, curr.lvl [2] 1})
	}
}

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

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' for left child's horizontal distance.

Using '-' for level increment.

For left child, horizontal distance decreases by 1 (hd - 1), level increases by 1 (lvl + 1). For right child, hd increases by 1 (hd + 1), level increases by 1 (lvl + 1).

4fill in blank

hard

Fill both blanks to correctly update the bottom view map during BFS.

DSA Go

if curr.lvl >= levelMap[curr.hd] {
	[1][curr.hd] = curr.lvl
	[2][curr.hd] = curr.node.data
}

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

AlevelMap

BhdMap

Cqueue

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing the two maps or using wrong variable names.

levelMap stores the max level for each horizontal distance; hdMap stores the node data for bottom view.

5fill in blank

hard

Fill all three blanks to create the final bottom view slice from the map.

DSA Go

keys := make([]int, 0, len([1]))
for k := range [2] {
	keys = append(keys, k)
}
sort.Ints(keys)
result := make([]int, 0, len(keys))
for _, k := range keys {
	result = append(result, [3][k])
}

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

AhdMap

BlevelMap

Dqueue

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up levelMap and hdMap when collecting keys or values.

We get keys from levelMap (horizontal distances), then append node data from hdMap in sorted order.