Top View of Binary Tree in DSA Go - Execution Trace

Concept Flow - Top View of Binary Tree

Start at root node

↓

Assign horizontal distance = 0

↓

Use queue for level order traversal

↓

Dequeue node

↓

Check if horizontal distance seen before?

↓

Add node to top view

↓

Enqueue left child with hd-1

↓

Enqueue right child with hd+1

↓

Repeat until queue empty

↓

Sort nodes by horizontal distance

↓

Print top view nodes

Traverse the tree level by level, track horizontal distances, and record the first node at each horizontal distance to get the top view.

Execution Sample

DSA Go

package main

import (
  "fmt"
  "sort"
)

type Node struct {
  Val   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}}
  m := make(map[int]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 := make([]int, 0, len(m))
  for k := range m {
    keys = append(keys, k)
  }
  sort.Ints(keys)
  res := make([]int, len(keys))
  for i, k := range keys {
    res[i] = m[k]
  }
  return res
}

func main() {
  root := &Node{Val: 1}
  root.Left = &Node{Val: 2}
  root.Right = &Node{Val: 3}
  root.Left.Left = &Node{Val: 4}
  root.Left.Right = &Node{Val: 5}
  root.Right.Left = &Node{Val: 6}
  root.Right.Right = &Node{Val: 7}

  topView := TopView(root)
  fmt.Println(topView) // Output: [4 2 1 3 7]
}

This code performs a breadth-first search on the binary tree, tracking horizontal distances to find the top view nodes.

Execution Table

Step	Operation	Current Node (Val)	Horizontal Distance (hd)	Top View Map (hd: node val)	Queue State (node val, hd)	Visual State
1	Start at root	1	0	{}	[(1,0)]	Root node 1 at hd=0
2	Dequeue node	1	0	{0:1}	[]	Add node 1 to top view at hd=0
3	Enqueue left child	2	-1	{0:1}	[(2,-1)]	Left child 2 at hd=-1
4	Enqueue right child	3	1	{0:1}	[(2,-1),(3,1)]	Right child 3 at hd=1
5	Dequeue node	2	-1	{0:1,-1:2}	[(3,1)]	Add node 2 to top view at hd=-1
6	Enqueue left child	4	-2	{0:1,-1:2}	[(3,1),(4,-2)]	Left child 4 at hd=-2
7	Enqueue right child	5	0	{0:1,-1:2}	[(3,1),(4,-2),(5,0)]	Right child 5 at hd=0 (hd=0 already seen, skip)
8	Dequeue node	3	1	{0:1,-1:2,1:3}	[(4,-2),(5,0)]	Add node 3 to top view at hd=1
9	Enqueue left child	6	0	{0:1,-1:2,1:3}	[(4,-2),(5,0),(6,0)]	Left child 6 at hd=0 (hd=0 seen, skip)
10	Enqueue right child	7	2	{0:1,-1:2,1:3}	[(4,-2),(5,0),(6,0),(7,2)]	Right child 7 at hd=2
11	Dequeue node	4	-2	{0:1,-1:2,1:3,-2:4}	[(5,0),(6,0),(7,2)]	Add node 4 to top view at hd=-2
12	Dequeue node	5	0	{0:1,-1:2,1:3,-2:4}	[(6,0),(7,2)]	hd=0 seen, skip node 5
13	Dequeue node	6	0	{0:1,-1:2,1:3,-2:4}	[(7,2)]	hd=0 seen, skip node 6
14	Dequeue node	7	2	{0:1,-1:2,1:3,-2:4,2:7}	[]	Add node 7 to top view at hd=2
15	Queue empty	-	-	{-2:4,-1:2,0:1,1:3,2:7}	[]	Traversal complete, top view collected

💡 Queue is empty, all nodes processed

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 11	After Step 14	Final
Queue	[(1,0)]	[]	[(3,1)]	[(4,-2),(5,0)]	[(5,0),(6,0),(7,2)]	[]	[]
Top View Map	{}	{0:1}	{0:1,-1:2}	{0:1,-1:2,1:3}	{0:1,-1:2,1:3,-2:4}	{-2:4,-1:2,0:1,1:3,2:7}	{-2:4,-1:2,0:1,1:3,2:7}

Key Moments - 3 Insights

Why do we only add a node to the top view map if its horizontal distance is not already present?

Because the top view shows the first node seen at each horizontal distance from the top. Later nodes at the same horizontal distance are hidden behind the first one. See execution_table rows 2, 5, 8, and 14 where nodes are added only if hd is new.

Why do we use a queue and BFS instead of DFS for top view?

BFS processes nodes level by level, ensuring the first node at each horizontal distance is the topmost. DFS might visit deeper nodes first, causing incorrect top view. The queue state in execution_table shows level order traversal.

What does the horizontal distance represent and how is it updated?

Horizontal distance (hd) measures how far left or right a node is from the root (hd=0). Left child hd = parent hd - 1, right child hd = parent hd + 1. This is shown in execution_table column 'Horizontal Distance (hd)'.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what nodes are in the top view map?

A {-1:2}

B {0:1}

C {0:1, -1:2}

D {}

💡 Hint

Check the 'Top View Map' column at step 5 in execution_table

At which step does the horizontal distance 2 first get added to the top view map?

A Step 14

B Step 10

C Step 7

D Step 11

💡 Hint

Look for when hd=2 appears in 'Top View Map' column in execution_table

If the node with value 5 was missing, how would the queue state change at step 7?

A Queue would be [(3,1),(4,-2)]

B Queue would be [(3,1),(4,-2),(7,2)]

C Queue would be [(3,1),(4,-2),(6,0),(7,2)]

D Queue would be [(3,1),(5,0),(6,0),(7,2)]

💡 Hint

Check enqueue operations in execution_table steps 6-10 and consider missing node 5

Concept Snapshot

Top View of Binary Tree:
- Use BFS (queue) with horizontal distance (hd) tracking
- Root hd = 0; left child hd = hd-1; right child hd = hd+1
- Record first node at each hd in a map
- After traversal, sort map by hd and print nodes
- Shows nodes visible from top, ignoring hidden ones

Full Transcript

To find the top view of a binary tree, we start at the root node with horizontal distance zero. We use a queue to do a level order traversal (BFS). For each node dequeued, if its horizontal distance is not yet recorded, we add it to the top view map. We enqueue left and right children with hd-1 and hd+1 respectively. This ensures the first node at each horizontal distance is recorded, representing the top view. After processing all nodes, we sort the recorded nodes by horizontal distance and print them. This method ensures we see the nodes visible from the top, ignoring nodes hidden behind others.

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