Top View of Binary Tree in DSA Go

Mental Model

We want to see the nodes visible when looking at the tree from above, ignoring nodes hidden behind others.

Analogy: Imagine standing on a balcony looking down at a garden with trees; you only see the tops of some branches, not the ones hidden behind.

       1
      / \
     2   3
      \   \
       4   5

Top view shows nodes: 2 -> 1 -> 3 -> 5

Dry Run Walkthrough

Input: Binary tree: 1 is root, 2 left child, 3 right child, 4 right child of 2, 5 right child of 3

Goal: Find nodes visible from top view: nodes that appear first at each horizontal distance from root

Step 1: Start at root node 1 with horizontal distance (hd) 0

Queue: [(1, hd=0)]
Top view map: {}

Why: We begin BFS from root to explore nodes level by level

Step 2: Visit node 1 at hd=0, add to top view map since hd=0 not seen before

Top view map: {0:1}
Queue: [(2, hd=-1), (3, hd=1)]

Why: First node at hd=0 is 1, add children with updated hd

Step 3: Visit node 2 at hd=-1, add to top view map since hd=-1 not seen before

Top view map: {-1:2, 0:1}
Queue: [(3, hd=1), (4, hd=0)]

Why: First node at hd=-1 is 2, add its right child with hd=0

Step 4: Visit node 3 at hd=1, add to top view map since hd=1 not seen before

Top view map: {-1:2, 0:1, 1:3}
Queue: [(4, hd=0), (5, hd=2)]

Why: First node at hd=1 is 3, add its right child with hd=2

Step 5: Visit node 4 at hd=0, skip adding to map since hd=0 already has node 1

Top view map unchanged: {-1:2, 0:1, 1:3}
Queue: [(5, hd=2)]

Why: Node 4 is hidden behind node 1 from top view

Step 6: Visit node 5 at hd=2, add to top view map since hd=2 not seen before

Top view map: {-1:2, 0:1, 1:3, 2:5}
Queue: []

Why: First node at hd=2 is 5

Result:

Top view nodes in order of hd: 2 -> 1 -> 3 -> 5

Annotated Code

DSA Go

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.Ints(keys)

Sort horizontal distances to print top view from left to right

Output

2 -> 1 -> 3 -> 5

Complexity Analysis

Time: O(n) because we visit each node once in BFS

Space: O(n) for queue and map storing nodes and horizontal distances

vs Alternative: Compared to DFS, BFS ensures first node at each horizontal distance is found level-wise, avoiding overwriting nodes visible from top

Edge Cases

Empty tree

Returns empty list since no nodes to view

DSA Go

if root == nil { return []int{} }

Tree with single node

Returns list with only root node value

DSA Go

if root == nil { return []int{} }

Multiple nodes at same horizontal distance but different levels

Only the topmost (first encountered in BFS) node is included

DSA Go

if _, exists := hdNodeMap[curr.hd]; !exists { hdNodeMap[curr.hd] = curr.node.Val }

When to Use This Pattern

When asked to find nodes visible from top or bottom in a binary tree, use BFS with horizontal distance tracking to capture first or last nodes at each horizontal distance.

Common Mistakes

Mistake: Using DFS which may overwrite nodes at same horizontal distance and miss top view nodes
Fix: Use BFS to ensure first node at each horizontal distance is recorded

Mistake: Not tracking horizontal distance, leading to incorrect nodes in top view
Fix: Track horizontal distance for each node relative to root

Summary

Finds nodes visible when looking at a binary tree from above by tracking horizontal distances.

Use when you need to print or find the top view of a binary tree.

The key is to record the first node encountered at each horizontal distance during a level order traversal.

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