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?

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

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

Visual Quiz - 3 Questions

Test your understanding

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{}

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.