Top View of Binary Tree in DSA Go - Build from Scratch

Top View of Binary Tree

📖 Scenario: Imagine you have a tree of family members, and you want to see who is visible if you look from the top. Some members might be hidden behind others. We will find the top view of a binary tree, which means the nodes visible when looking from above.

🎯 Goal: Build a program that creates a binary tree, sets a horizontal distance limit, finds the top view nodes of the tree, and prints them in order from left to right.

📋 What You'll Learn

Create a binary tree with exact nodes and structure

Use a variable to track horizontal distance

Implement logic to find the top view of the binary tree

Print the top view nodes in order

💡 Why This Matters

🌍 Real World

Top view of a binary tree helps in visualizing hierarchical data from a specific perspective, useful in network routing, organizational charts, and graphical rendering.

💼 Career

Understanding tree traversals and views is important for software engineers working with data structures, algorithms, and system design.

1

Create the binary tree structure

Create a struct called Node with data int, left *Node, and right *Node. Then create the binary tree with root node having data 1, left child 2, right child 3, left child of 2 as 4, and right child of 2 as 5.

DSA Go

// Define Node struct and create the binary tree as described
// Your code here

Hint

Define the Node struct first, then create nodes and link them as left and right children.

2

Add a map to track horizontal distances

Create a variable called topViewMap of type map[int]int to store the first node data at each horizontal distance. Also create a variable minHD and set it to 0, and maxHD and set it to 0 to track the minimum and maximum horizontal distances.

DSA Go

package main

import "fmt"

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

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}

	// Create map and variables for horizontal distance
	// Your code here
}

Hint

Use make to create the map and initialize minHD and maxHD to zero.

3

Implement the top view traversal logic

Write a function topView that takes root *Node, hd int, topViewMap map[int]int, and pointers to minHD and maxHD. Traverse the tree recursively. If hd is not in topViewMap, add root.data. Update minHD and maxHD accordingly. Call topView for left child with hd-1 and right child with hd+1. Call this function from main with hd=0.

DSA Go

package main

import "fmt"

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

func topView(root *Node, hd int, topViewMap map[int]int, minHD *int, maxHD *int) {
	// Your code here
}

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}

	topViewMap := make(map[int]int)
	minHD := 0
	maxHD := 0

	// Call topView function here

}

Hint

Use recursion to visit nodes. Store the first node at each horizontal distance. Update min and max horizontal distances.

4

Print the top view nodes from left to right

Use a for loop from minHD to maxHD inclusive. Print the values from topViewMap for each horizontal distance separated by spaces.

DSA Go

package main

import "fmt"

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

func topView(root *Node, hd int, topViewMap map[int]int, minHD *int, maxHD *int) {
	if root == nil {
		return
	}
	if _, ok := topViewMap[hd]; !ok {
		topViewMap[hd] = root.data
	}
	if hd  *maxHD {
		*maxHD = hd
	}
	topView(root.left, hd-1, topViewMap, minHD, maxHD)
	topView(root.right, hd+1, topViewMap, minHD, maxHD)
}

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}

	topViewMap := make(map[int]int)
	minHD := 0
	maxHD := 0

	topView(root, 0, topViewMap, &minHD, &maxHD)

	// Your code here
}

Hint

Loop from minHD to maxHD and print the values from the map with spaces.