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.

Practice

1. What does the top view of a binary tree represent?

easy

A. All leaf nodes of the tree

B. Nodes visible when the tree is viewed from the left side

C. Nodes visible when the tree is viewed from above

D. Nodes visible when the tree is viewed from the right side

Solution

1. Step 1: Understand the top view concept

   The top view of a binary tree includes all nodes visible when looking down vertically from above the tree.

2. Step 2: Differentiate from other views

   Left or right views show nodes from side angles, while top view shows nodes from above.

3. Final Answer:

   Nodes visible when the tree is viewed from above -> Option C

4. Quick Check:

   Top view = nodes seen from above [OK]

Hint: Top view shows nodes visible from above only [OK]

Common Mistakes:

• Confusing top view with left or right view
• Including all leaf nodes as top view
• Thinking top view shows all nodes

2. Which Go data structure is best suited to store nodes for computing the top view of a binary tree?

easy

A. Map with horizontal distance as key

B. Array

C. Slice

D. Linked list

Solution

1. Step 1: Identify the need for horizontal distance mapping

   Top view requires tracking nodes by their horizontal distance from root to avoid duplicates.

2. Step 2: Choose data structure supporting key-value pairs

   A map with horizontal distance as key stores the first node at each horizontal distance efficiently.

3. Final Answer:

   Map with horizontal distance as key -> Option A

4. Quick Check:

   Use map for horizontal distance keys [OK]

Hint: Use map keyed by horizontal distance for top view [OK]

Common Mistakes:

• Using slice or array without horizontal distance keys
• Using linked list which lacks key access
• Ignoring horizontal distance concept

3. Given the following Go code snippet for top view, what will be printed?

type Node struct {
  Val int
  Left, Right *Node
}

func topView(root *Node) []int {
  if root == nil {
    return []int{}
  }
  type pair struct { node *Node; hd int }
  queue := []pair{{root, 0}}
  m := map[int]int{}
  res := []int{}

  for len(queue) > 0 {
    p := queue[0]
    queue = queue[1:]
    if _, ok := m[p.hd]; !ok {
      m[p.hd] = p.node.Val
    }
    if p.node.Left != nil {
      queue = append(queue, pair{p.node.Left, p.hd - 1})
    }
    if p.node.Right != nil {
      queue = append(queue, pair{p.node.Right, p.hd + 1})
    }
  }

  keys := []int{}
  for k := range m {
    keys = append(keys, k)
  }
  sort.Ints(keys)
  for _, k := range keys {
    res = append(res, m[k])
  }
  return res
}

root := &Node{Val: 1}
root.Left = &Node{Val: 2}
root.Right = &Node{Val: 3}
root.Left.Right = &Node{Val: 4}
root.Left.Right.Right = &Node{Val: 5}
root.Left.Right.Right.Right = &Node{Val: 6}

fmt.Println(topView(root))

medium

A. [2 1 3]

B. [2 1 3 6]

C. [2 1 4 5 6]

D. [1 2 3 4 5 6]

Solution

1. Step 1: Traverse nodes with horizontal distances

   Root(1) at hd=0, Left(2) at hd=-1, Right(3) at hd=1, Left.Right(4) at hd=0 (ignored), Left.Right.Right(5) at hd=1 (ignored), Left.Right.Right.Right(6) at hd=2.

2. Step 2: Collect first nodes at each horizontal distance

   hd=-1:2, hd=0:1, hd=1:3, hd=2:6

3. Final Answer:

   [2 1 3 6] -> Option B

4. Quick Check:

   Top view nodes by hd sorted: 2,1,3,6 [OK]

Hint: First node at each horizontal distance forms top view [OK]

Common Mistakes:

• Including nodes overwritten at same horizontal distance
• Ignoring horizontal distance ordering
• Confusing top view with level order

4. The following Go code attempts to compute the top view of a binary tree but has a bug. What is the bug?

func topView(root *Node) []int {
  if root == nil {
    return []int{}
  }
  type pair struct { node *Node; hd int }
  queue := []pair{{root, 0}}
  m := map[int]int{}
  res := []int{}

  for len(queue) > 0 {
    p := queue[0]
    queue = queue[1:]
    m[p.hd] = p.node.Val
    if p.node.Left != nil {
      queue = append(queue, pair{p.node.Left, p.hd - 1})
    }
    if p.node.Right != nil {
      queue = append(queue, pair{p.node.Right, p.hd + 1})
    }
  }

  keys := []int{}
  for k := range m {
    keys = append(keys, k)
  }
  sort.Ints(keys)
  for _, k := range keys {
    res = append(res, m[k])
  }
  return res
}

medium

A. It overwrites nodes at the same horizontal distance, losing top view nodes

B. It does not handle nil root properly

C. It uses a slice instead of a queue

D. It does not sort the keys before output

Solution

1. Step 1: Analyze map assignment inside loop

   The code assigns m[p.hd] = p.node.Val every time, overwriting previous values at same horizontal distance.

2. Step 2: Understand top view requirement

   Top view requires storing only the first node encountered at each horizontal distance, so overwriting causes incorrect output.

3. Final Answer:

   It overwrites nodes at the same horizontal distance, losing top view nodes -> Option A

4. Quick Check:

   Overwrite causes wrong top view [OK]

Hint: Store first node per horizontal distance only [OK]

Common Mistakes:

• Overwriting map entries instead of checking existence
• Ignoring horizontal distance uniqueness
• Not sorting keys before output

5. You have a binary tree where multiple nodes share the same horizontal distance and level. How should you modify the top view algorithm to always show the node with the smallest value at each horizontal distance?

hard

A. Store the last node encountered at each horizontal distance regardless of value

B. Use a stack instead of a queue for traversal

C. Ignore horizontal distance and print all nodes at the top level

D. Store the node with the smallest value for each horizontal distance, updating if a smaller value is found

Solution

1. Step 1: Understand the problem with duplicates

   When nodes share horizontal distance and level, top view must pick one node per horizontal distance.

2. Step 2: Modify map to track smallest value

   Instead of storing first node only, update stored node if a smaller value is found at the same horizontal distance.

3. Step 3: Implement comparison logic

   Check if current node's value is smaller than stored; if yes, replace it in the map.

4. Final Answer:

   Store the node with the smallest value for each horizontal distance, updating if a smaller value is found -> Option D

5. Quick Check:

   Keep smallest value per horizontal distance [OK]

Hint: Update map only if new node value is smaller [OK]

Common Mistakes:

• Ignoring node values when duplicates occur
• Using last node instead of smallest value
• Changing traversal order instead of map logic