Top View of Binary Tree in DSA Go - Deep Dive

Overview - Top View of Binary Tree

What is it?

The top view of a binary tree is the set of nodes visible when the tree is seen from above. Imagine looking down on the tree and noting which nodes appear first at each horizontal position. This view shows the nodes that are not hidden behind others when seen from the top.

Why it matters

Without the concept of top view, we cannot easily understand how a tree looks from different perspectives, which is important in visualization and certain algorithms. It helps in problems where we want to see the outline or skyline of a tree structure, useful in graphics, network routing, and hierarchical data representation.

Where it fits

Before learning top view, you should understand binary trees, tree traversal methods, and the concept of horizontal distance in trees. After this, you can explore related views like bottom view, left view, and right view of binary trees, and advanced tree algorithms.

Mental Model

Core Idea

The top view of a binary tree shows the first node encountered at each horizontal distance from the root when looking down from above.

Think of it like...

Imagine standing on a hill looking down at a forest of trees. The top view is like seeing only the tallest tree at each spot on the ground, ignoring any trees hidden behind others.

          (0)
         Root
        /    \
   (-1) L      R (1)
    /            \
 (-2)LL          RR(2)

Horizontal distances:
-2  -1   0   1   2

Top view picks first nodes at each horizontal distance:
LL -> L -> Root -> R -> RR

Build-Up - 7 Steps

1

Foundation

Understanding Binary Tree Structure

Concept: Learn what a binary tree is and how nodes connect with left and right children.

A binary tree is a structure where each node has up to two children: left and right. The top node is called the root. Each child can itself be a root of a subtree. This structure allows hierarchical data representation.

Result

You can represent data in a tree form where each node connects to up to two others.

Understanding the basic tree structure is essential because top view depends on how nodes are arranged horizontally and vertically.

2

Foundation

Horizontal Distance Concept in Trees

Concept: Introduce horizontal distance (HD) to measure node positions relative to the root.

Assign the root node a horizontal distance of 0. For any node, its left child has HD = parent's HD - 1, and right child has HD = parent's HD + 1. This helps track nodes' horizontal positions.

Result

You can now label each node with a number showing how far left or right it is from the root.

Horizontal distance is the key to identifying which nodes appear in the top view at each horizontal position.

3

Intermediate

Level Order Traversal with Horizontal Distance

🤔Before reading on: Do you think a depth-first or breadth-first traversal better captures the top view? Commit to your answer.

Concept: Use breadth-first (level order) traversal to visit nodes level by level while tracking horizontal distances.

Traverse the tree level by level using a queue. For each node, record its horizontal distance. This order ensures the first node encountered at each horizontal distance is the topmost node.

Result

You get nodes in order of their depth and horizontal position, allowing you to pick the top view nodes correctly.

Using level order traversal ensures you see nodes from top to bottom, so the first node at each horizontal distance is the visible one from the top.

4

Intermediate

Mapping Horizontal Distance to Nodes

🤔Before reading on: Do you think multiple nodes can share the same horizontal distance? Commit to yes or no.

Concept: Store the first node encountered at each horizontal distance in a map or dictionary.

While traversing, check if the horizontal distance is already in the map. If not, add the current node. If yes, skip because the first node is the top view node for that distance.

Result

A map from horizontal distance to node value representing the top view.

Knowing that only the first node at each horizontal distance matters prevents overwriting and keeps the correct top view.

5

Intermediate

Extracting and Printing the Top View

Concept: After traversal, sort the horizontal distances and print the corresponding nodes.

Collect all keys (horizontal distances) from the map, sort them from smallest to largest, and print the node values in that order. This shows the top view from left to right.

Result

A sequence of node values representing the top view of the binary tree.

Sorting horizontal distances ensures the top view is presented in the natural left-to-right order.

6

Advanced

Complete Go Implementation of Top View

🤔Before reading on: Do you think the queue should store nodes only or nodes with extra info? Commit to your answer.

Concept: Implement the top view algorithm in Go using a queue that stores nodes along with their horizontal distances.

package main import ( "fmt" ) type Node struct { Val int Left *Node Right *Node } type QueueItem struct { Node *Node HD int } func topView(root *Node) { if root == nil { return } queue := []QueueItem{{root, 0}} hdMap := make(map[int]int) minHD, maxHD := 0, 0 for len(queue) > 0 { item := queue[0] queue = queue[1:] node, hd := item.Node, item.HD if _, exists := hdMap[hd]; !exists { hdMap[hd] = node.Val } if node.Left != nil { queue = append(queue, QueueItem{node.Left, hd - 1}) if hd-1 < minHD { minHD = hd - 1 } } if node.Right != nil { queue = append(queue, QueueItem{node.Right, hd + 1}) if hd+1 > maxHD { maxHD = hd + 1 } } } for i := minHD; i <= maxHD; i++ { if val, ok := hdMap[i]; ok { fmt.Printf("%d ", val) } } fmt.Println() } func main() { 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} topView(root) }

Result

1 2 4 5 6 3

Storing nodes with their horizontal distances in the queue allows tracking positions during traversal, enabling correct top view extraction.

7

Expert

Handling Edge Cases and Optimizations

🤔Before reading on: Do you think nodes at the same horizontal distance but different depths can both appear in the top view? Commit to yes or no.

Concept: Understand how the algorithm handles nodes overlapping horizontally and optimize space usage.

Nodes at the same horizontal distance but deeper levels are hidden behind the first encountered node at that distance. The algorithm ignores them for top view. To optimize, use a balanced tree or limit queue size by pruning unnecessary nodes. Also, consider iterative vs recursive approaches for large trees.

Result

The top view correctly shows only the visible nodes, and the algorithm runs efficiently even for large trees.

Knowing that only the first node at each horizontal distance matters prevents unnecessary processing and helps optimize performance.

Under the Hood

The algorithm uses a breadth-first search (level order traversal) combined with horizontal distance tracking. Each node is paired with its horizontal distance from the root. A map stores the first node encountered at each horizontal distance. Because BFS visits nodes level by level, the first node at a horizontal distance is the topmost visible node. The map prevents overwriting nodes at the same horizontal distance but deeper levels.

Why designed this way?

This approach ensures the top view reflects the nodes visible from above, respecting both horizontal position and vertical depth. Alternatives like depth-first search can miss the topmost nodes because they explore one branch deeply before others. BFS guarantees correct order. Using a map keyed by horizontal distance efficiently tracks visibility without storing all nodes.

┌───────────────┐
│    Queue      │
│  (Node, HD)   │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Level Order   │
│ Traversal     │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Map HD -> Node│
│ (first only)  │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Sort HD keys  │
│ Print nodes   │
└───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does the top view include all nodes at a horizontal distance or only the first one? Commit to your answer.

Common Belief: The top view includes all nodes at the same horizontal distance.

Reality: Only the first node encountered at each horizontal distance (the topmost) is included in the top view.

Why it matters: Including all nodes would show hidden nodes behind others, breaking the definition of top view and causing incorrect visualizations.

Quick: Is depth-first traversal sufficient to get the correct top view? Commit yes or no.

Common Belief: Depth-first traversal can be used to find the top view just as well as breadth-first traversal.

Reality: Depth-first traversal can miss the topmost nodes because it explores one branch deeply before others, so it may overwrite nodes incorrectly.

Why it matters: Using DFS can lead to wrong top view results, especially in unbalanced trees, causing bugs in applications relying on accurate views.

Quick: Can nodes with the same horizontal distance but different depths both appear in the top view? Commit yes or no.

Common Belief: All nodes at the same horizontal distance appear in the top view regardless of depth.

Reality: Only the node closest to the root (smallest depth) at each horizontal distance appears in the top view.

Why it matters: Ignoring depth leads to showing nodes hidden behind others, which misrepresents the tree's visible outline.

Quick: Does the top view depend on the order of insertion of nodes? Commit yes or no.

Common Belief: The order in which nodes are inserted affects the top view output.

Reality: The top view depends only on the tree structure and node positions, not insertion order.

Why it matters: Misunderstanding this can cause confusion when different insertion orders produce the same top view, leading to incorrect assumptions about tree uniqueness.

Expert Zone

1

The top view algorithm implicitly assumes a unique horizontal distance for each vertical line; overlapping nodes at the same HD but different depths are resolved by BFS order.

2

In trees with large depth and width, memory usage can be optimized by pruning nodes that cannot affect the top view once a node at that HD is recorded.

3

The top view can be extended to weighted or threaded binary trees by adjusting horizontal distance calculations and traversal methods.

When NOT to use

Top view is not suitable when you need to see all nodes at each horizontal distance or when vertical order traversal is required. For full visibility, use vertical order traversal or bottom view instead.

Production Patterns

Top view is used in graphical rendering of hierarchical data, network topology visualization, and in algorithms that require skyline or silhouette extraction from tree-like data. It is also a common interview problem to test understanding of BFS and tree traversal.

Connections

Bottom View of Binary Tree

Opposite perspective of top view, showing nodes visible from below.

Understanding top view helps grasp bottom view since both use horizontal distance but differ in which node at each distance is visible.

Breadth-First Search (BFS)

Top view relies on BFS traversal to visit nodes level by level.

Knowing BFS deeply clarifies why the first node at each horizontal distance is the top view node.

Urban Skyline Problem (Computational Geometry)

Both problems involve finding visible outlines from a viewpoint, using horizontal positions and heights.

Recognizing this connection shows how tree views relate to real-world skyline computations, bridging data structures and geometry.

Common Pitfalls

#1 Overwriting nodes at the same horizontal distance during traversal.

Wrong approach:

if _, exists := hdMap[hd]; exists {
hdMap[hd] = node.Val
}

Correct approach:

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

Root cause:

Misunderstanding that only the first node at each horizontal distance should be recorded, leading to overwriting and incorrect top view.

#2 Using depth-first traversal without tracking levels properly.

Wrong approach:

func dfs(node *Node, hd int) {
hdMap[hd] = node.Val
if node.Left != nil {
dfs(node.Left, hd-1)
}
if node.Right != nil {
dfs(node.Right, hd+1)
}
}

Correct approach:

Use BFS with queue storing nodes and their horizontal distances to ensure first node at each HD is recorded.

Root cause:

DFS visits nodes in depth order, not level order, causing deeper nodes to overwrite shallower ones.

#3 Not sorting horizontal distances before printing results.

Wrong approach:

for hd, val := range hdMap {
fmt.Printf("%d ", val)
}

Correct approach:

keys := []int{}
for k := range hdMap {
keys = append(keys, k)
}
sort.Ints(keys)
for _, k := range keys {
fmt.Printf("%d ", hdMap[k])
}

Root cause:

Maps in Go do not guarantee order, so printing without sorting leads to unordered output.

Key Takeaways

The top view of a binary tree shows the first node visible at each horizontal distance from the root when viewed from above.

Horizontal distance is a crucial concept that assigns a position to each node relative to the root, enabling the top view calculation.

Breadth-first traversal ensures nodes are visited level by level, allowing the algorithm to pick the topmost node at each horizontal distance correctly.

Only the first node encountered at each horizontal distance is part of the top view; deeper nodes at the same distance are hidden.

Sorting the horizontal distances before outputting the nodes ensures the top view is presented from left to right.

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