Top View of Binary Tree in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Top View for a Simple Binary Tree

What is the output of the top view traversal for the given binary tree?

DSA Go

package main

import "fmt"

type Node struct {
    data  int
    left  *Node
    right *Node
}

func topView(root *Node) []int {
    if root == nil {
        return []int{}
    }
    type pair struct {
        node *Node
        hd   int
    }
    queue := []pair{{root, 0}}
    hdMap := map[int]int{}
    minHd, maxHd := 0, 0
    result := []int{}

    for len(queue) > 0 {
        p := queue[0]
        queue = queue[1:]
        node, hd := p.node, p.hd

        if _, ok := hdMap[hd]; !ok {
            hdMap[hd] = node.data
            if hd < minHd {
                minHd = hd
            }
            if hd > maxHd {
                maxHd = hd
            }
        }

        if node.left != nil {
            queue = append(queue, pair{node.left, hd - 1})
        }
        if node.right != nil {
            queue = append(queue, pair{node.right, hd + 1})
        }
    }

    for i := minHd; i <= maxHd; i++ {
        result = append(result, hdMap[i])
    }
    return result
}

func main() {
    root := &Node{data: 1}
    root.left = &Node{data: 2}
    root.right = &Node{data: 3}
    root.left.right = &Node{data: 4}
    root.left.right.right = &Node{data: 5}
    root.left.right.right.right = &Node{data: 6}

    fmt.Println(topView(root))
}

A [2, 1, 3, 6]

B [1, 2, 3]

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

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

💡 Hint

Think about horizontal distances and which nodes appear first at each horizontal distance.

The top view includes the first node encountered at each horizontal distance from the root. Nodes 2, 1, 3, and 6 are visible from the top.

🧠 Conceptual

intermediate

Understanding Horizontal Distance in Top View

In the context of the top view of a binary tree, what does the 'horizontal distance' (hd) represent?

A The vertical level of a node from the root

B The distance of a node from the root measured horizontally, with root at 0, left child at hd-1, right child at hd+1

C The depth of a node in the tree

D The number of nodes between the root and the current node

💡 Hint

Horizontal distance helps to identify nodes aligned vertically when viewed from the top.

Horizontal distance is used to track the position of nodes relative to the root horizontally. Left child decreases hd by 1, right child increases hd by 1.

🔧 Debug

advanced

Identify the Bug in Top View Implementation

What error will occur when running this code snippet for top view of a binary tree?

DSA Go

func topView(root *Node) []int {
    if root == nil {
        return []int{}
    }
    type pair struct {
        node *Node
        hd   int
    }
    queue := []pair{{root, 0}}
    hdMap := map[int]int{}
    minHd, maxHd := 0, 0
    result := []int{}

    for len(queue) > 0 {
        p := queue[0]
        queue = queue[1:]
        node, hd := p.node, p.hd

        hdMap[hd] = node.data
        if hd < minHd {
            minHd = hd
        }
        if hd > maxHd {
            maxHd = hd
        }

        if node.left != nil {
            queue = append(queue, pair{node.left, hd - 1})
        }
        if node.right != nil {
            queue = append(queue, pair{node.right, hd + 1})
        }
    }

    for i := minHd; i <= maxHd; i++ {
        result = append(result, hdMap[i])
    }
    return result
}

A Infinite loop because queue is never emptied

B Syntax error due to missing colon in map declaration

C The map overwrites values, so the top view is incorrect

D Runtime panic due to nil pointer dereference

💡 Hint

Check how the map is updated for each horizontal distance.

The code overwrites the map value for each horizontal distance, so the last node at that hd is stored, not the first visible node.

🚀 Application

advanced

Top View of a Complex Binary Tree

Given the binary tree below, what is the top view output? Tree structure: 10 / \ 20 30 / \ \ 40 60 50 / \ 70 80

A [40, 20, 60, 10, 30, 50, 80]

B [40, 20, 10, 30, 50]

C [20, 10, 30, 50, 80]

D [40, 20, 10, 30, 50, 80]

💡 Hint

Consider horizontal distances and which nodes appear first at each horizontal distance.

Nodes visible from top are the first nodes at horizontal distances -2, -1, 0, 1, 2, and 3: 40, 20, 10, 30, 50, 80.

❓ Predict Output

expert

Output of Top View with Multiple Nodes at Same Horizontal Distance

What is the output of the top view traversal for the following binary tree? Tree: 1 / \ 2 3 / \ \ 4 5 6 \ \ 7 8

DSA Go

package main

import "fmt"

type Node struct {
    data  int
    left  *Node
    right *Node
}

func topView(root *Node) []int {
    if root == nil {
        return []int{}
    }
    type pair struct {
        node *Node
        hd   int
    }
    queue := []pair{{root, 0}}
    hdMap := map[int]int{}
    minHd, maxHd := 0, 0
    result := []int{}

    for len(queue) > 0 {
        p := queue[0]
        queue = queue[1:]
        node, hd := p.node, p.hd

        if _, ok := hdMap[hd]; !ok {
            hdMap[hd] = node.data
            if hd < minHd {
                minHd = hd
            }
            if hd > maxHd {
                maxHd = hd
            }
        }

        if node.left != nil {
            queue = append(queue, pair{node.left, hd - 1})
        }
        if node.right != nil {
            queue = append(queue, pair{node.right, hd + 1})
        }
    }

    for i := minHd; i <= maxHd; i++ {
        result = append(result, hdMap[i])
    }
    return result
}

func main() {
    root := &Node{data: 1}
    root.left = &Node{data: 2}
    root.right = &Node{data: 3}
    root.left.left = &Node{data: 4}
    root.left.right = &Node{data: 5}
    root.right.right = &Node{data: 6}
    root.left.right.right = &Node{data: 7}
    root.right.right.right = &Node{data: 8}

    fmt.Println(topView(root))
}

A [4, 2, 1, 3, 6, 8]

B [4, 2, 1, 5, 6, 8]

C [2, 1, 3, 6, 8]

D [4, 2, 1, 3, 7, 8]

💡 Hint

Remember only the first node at each horizontal distance is included in the top view.

Nodes 4, 2, 1, 3, 6, and 8 are the first nodes at horizontal distances -2, -1, 0, 1, 2, and 3 respectively.