package main
import (
"container/list"
"fmt"
"sort"
)
type Node struct {
Val int
Left *Node
Right *Node
}
func topView(root *Node) []int {
if root == nil {
return []int{}
}
// Map to store first node at each horizontal distance
hdNodeMap := make(map[int]int)
// Queue for BFS: stores pairs of node and its horizontal distance
queue := list.New()
queue.PushBack(struct {
node *Node
hd int
}{root, 0})
for queue.Len() > 0 {
front := queue.Front()
queue.Remove(front)
curr := front.Value.(struct {
node *Node
hd int
})
// If hd not seen before, add node value
if _, exists := hdNodeMap[curr.hd]; !exists {
hdNodeMap[curr.hd] = curr.node.Val
}
// Add left child with hd-1
if curr.node.Left != nil {
queue.PushBack(struct {
node *Node
hd int
}{curr.node.Left, curr.hd - 1})
}
// Add right child with hd+1
if curr.node.Right != nil {
queue.PushBack(struct {
node *Node
hd int
}{curr.node.Right, curr.hd + 1})
}
}
// Extract keys and sort to print top view from left to right
keys := []int{}
for k := range hdNodeMap {
keys = append(keys, k)
}
sort.Ints(keys)
result := []int{}
for _, k := range keys {
result = append(result, hdNodeMap[k])
}
return result
}
func main() {
// Construct tree:
// 1
// / \
// 2 3
// \ \
// 4 5
root := &Node{Val: 1}
root.Left = &Node{Val: 2}
root.Right = &Node{Val: 3}
root.Left.Right = &Node{Val: 4}
root.Right.Right = &Node{Val: 5}
tv := topView(root)
for i, v := range tv {
if i > 0 {
fmt.Print(" -> ")
}
fmt.Print(v)
}
fmt.Println()
}
queue.PushBack(struct { node *Node; hd int }{root, 0})
Initialize BFS queue with root at horizontal distance 0
front := queue.Front()
queue.Remove(front)
curr := front.Value.(struct { node *Node; hd int })
Dequeue current node and its horizontal distance for processing
if _, exists := hdNodeMap[curr.hd]; !exists { hdNodeMap[curr.hd] = curr.node.Val }
Add node value to map if this horizontal distance is seen first time
if curr.node.Left != nil { queue.PushBack(struct { node *Node; hd int }{curr.node.Left, curr.hd - 1}) }
Add left child with horizontal distance decreased by 1
if curr.node.Right != nil { queue.PushBack(struct { node *Node; hd int }{curr.node.Right, curr.hd + 1}) }
Add right child with horizontal distance increased by 1
Sort horizontal distances to print top view from left to right