Top View of Binary Tree in DSA Typescript - 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 you can see without any other nodes blocking them. This view shows the nodes that appear first at each horizontal distance from the root.

Why it matters

Without the concept of top view, we would miss understanding how a tree looks from different perspectives, which is important in many applications like graphical representations, network routing, and spatial data structures. It helps us visualize and process hierarchical data in a way that reflects real-world views.

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.

Mental Model

Core Idea

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

Think of it like...

Imagine standing on a balcony looking down at a group of trees planted in a line. Some trees are taller and block others behind them. The top view is like noting which tree tops you can see from your spot, ignoring the ones hidden behind taller trees.

          (root)
           │
   ┌───────┴───────┐
  (L)             (R)

Horizontal distances:
  L: -1, root: 0, R: +1

Top view picks one node per horizontal distance:
  -1 -> left node
   0 -> root
  +1 -> right node

Build-Up - 6 Steps

1

Foundation

Understanding Binary Trees Basics

Concept: Learn what a binary tree is and how nodes are connected.

A binary tree is a structure where each node has up to two children: left and right. The top node is called the root. Nodes connect downwards forming branches.

Result

You can identify root, left child, right child, and leaf nodes in a binary tree.

Understanding the basic structure of binary trees is essential before exploring views like the top view.

2

Foundation

Horizontal Distance Concept

Concept: Introduce horizontal distance to locate nodes relative to root.

Assign horizontal distance (HD) to nodes: root is 0, left child is HD - 1, right child is HD + 1. This helps map nodes to positions on a horizontal line.

Result

Each node has a horizontal distance value showing its position relative to root.

Horizontal distance lets us group nodes vertically, which is key to finding the top view.

3

Intermediate

Level Order Traversal with Horizontal Distance

🤔Before reading on: do you think a simple preorder traversal can find the top view correctly? Commit to yes or no.

Concept: Use level order traversal (breadth-first) combined with horizontal distance to visit nodes level by level.

Traverse the tree level by level using a queue. Track each node's horizontal distance. For each HD, record the first node encountered.

Result

You get the first node at each horizontal distance, which forms the top view.

Level order traversal ensures nodes closer to the root are processed first, capturing the topmost nodes per horizontal distance.

4

Intermediate

Storing and Updating Top View Nodes

🤔Before reading on: do you think nodes at the same horizontal distance but lower levels replace earlier nodes in top view? Commit to yes or no.

Concept: Maintain a map from horizontal distance to node value, only set once per HD during traversal.

When visiting a node, if its HD is not in the map, add it. If it is already present, skip updating to keep the topmost node.

Result

The map contains exactly one node per horizontal distance, representing the top view.

Knowing to keep only the first node per horizontal distance prevents overwriting and preserves the correct top view.

5

Advanced

Implementing Top View in TypeScript

🤔Before reading on: do you think the output order of top view nodes should be sorted by horizontal distance? Commit to yes or no.

Concept: Write a complete TypeScript function to compute and print the top view nodes in order from leftmost to rightmost.

Use a queue for level order traversal, a map for HD to node, and track min and max HD to print in order. Code: class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; constructor(val: number) { this.val = val; this.left = null; this.right = null; } } function topView(root: TreeNode | null): void { if (!root) return; const queue: Array<{node: TreeNode; hd: number}> = []; const hdNodeMap = new Map(); let minHd = 0, maxHd = 0; queue.push({node: root, hd: 0}); while (queue.length > 0) { const {node, hd} = queue.shift()!; if (!hdNodeMap.has(hd)) { hdNodeMap.set(hd, node.val); } if (node.left) queue.push({node: node.left, hd: hd - 1}); if (node.right) queue.push({node: node.right, hd: hd + 1}); if (hd < minHd) minHd = hd; if (hd > maxHd) maxHd = hd; } const result: number[] = []; for (let i = minHd; i <= maxHd; i++) { if (hdNodeMap.has(i)) { result.push(hdNodeMap.get(i)!); } } console.log(result.join(' -> ') + ' -> null'); } // Example usage: // Construct tree: // 1 // / \ // 2 3 // \ \ // 4 5 // topView should print: 2 -> 1 -> 3 -> 5 -> null const root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.right = new TreeNode(4); root.right.right = new TreeNode(5); topView(root);

Result

2 -> 1 -> 3 -> 5 -> null

Implementing the algorithm in code solidifies understanding and shows how traversal and mapping combine to produce the top view.

6

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think the top view algorithm changes if the tree is very unbalanced? Commit to yes or no.

Concept: Consider trees with only left or right children, and analyze time and space complexity.

In skewed trees, horizontal distances become negative or positive extremes but the algorithm still works. The time complexity is O(n) because each node is visited once. Space complexity is O(n) due to the queue and map. Optimizations include using ordered maps or arrays if HD range is known.

Result

The algorithm correctly handles all tree shapes efficiently.

Understanding edge cases and complexity ensures the algorithm is robust and scalable in real applications.

Under the Hood

The algorithm uses a breadth-first search (level order traversal) to visit nodes level by level. Each node is assigned a horizontal distance relative to the root. A map stores the first node encountered at each horizontal distance. Because BFS visits nodes closer to the root first, the first node at each horizontal distance is the topmost visible node. The map keys represent horizontal distances, and values are node values. After traversal, nodes are output in order from the smallest to largest horizontal distance.

Why designed this way?

This approach was chosen because BFS naturally processes nodes by depth, ensuring the topmost nodes are recorded first. Using horizontal distance groups nodes vertically, allowing a simple map to track visibility. Alternatives like DFS do not guarantee visiting top nodes first, making BFS the preferred method. The design balances simplicity, correctness, and efficiency.

┌───────────────┐
│   Start root  │
└──────┬────────┘
       │ hd=0
       ▼
┌───────────────┐
│ Enqueue root  │
└──────┬────────┘
       │
       ▼
┌─────────────────────────────┐
│ While queue not empty:       │
│  Dequeue node and hd         │
│  If hd not in map:           │
│    map[hd] = node.val        │
│  Enqueue left child hd-1     │
│  Enqueue right child hd+1    │
└─────────────┬───────────────┘
              │
              ▼
┌─────────────────────────────┐
│ After traversal:             │
│  Print map values sorted by  │
│  hd from min to max          │
└─────────────────────────────┘

Myth Busters - 3 Common Misconceptions

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

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

Reality: The top view includes only the first node encountered at each horizontal distance during level order traversal.

Why it matters: Including all nodes would show multiple nodes per horizontal distance, which is incorrect and confuses the actual visible nodes from the top.

Quick: Can preorder traversal alone correctly find the top view? Commit to yes or no.

Common Belief: Preorder traversal is enough to find the top view.

Reality: Preorder traversal does not guarantee visiting nodes in order of depth, so it can miss the topmost nodes at some horizontal distances.

Why it matters: Using preorder can lead to incorrect top views because deeper nodes might overwrite shallower ones.

Quick: Does the order of printing top view nodes matter? Commit to yes or no.

Common Belief: The order of nodes in the top view output does not matter.

Reality: The top view nodes must be printed from the smallest to largest horizontal distance to reflect the left-to-right order.

Why it matters: Incorrect order confuses the spatial layout and misrepresents the tree's top view.

Expert Zone

1

Horizontal distance can be negative or positive, so using a map keyed by HD is essential instead of arrays indexed by HD.

2

In trees with overlapping nodes at the same horizontal distance and level, the first encountered node in BFS is chosen, which depends on traversal order.

3

Tracking min and max horizontal distances during traversal allows efficient ordered output without sorting the map keys afterward.

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 those cases, use vertical order traversal or bottom view algorithms instead.

Production Patterns

Top view is used in graphical rendering of trees, network topology visualization, and spatial indexing where a simplified visible outline is needed. It also helps in problems involving line-of-sight or visibility in hierarchical data.

Connections

Vertical Order Traversal

Builds-on

Understanding top view helps grasp vertical order traversal, which extends the idea by listing all nodes per horizontal distance, ordered by depth.

Breadth-First Search (BFS)

Same pattern

Top view relies on BFS traversal to process nodes level by level, showing how BFS is fundamental in many tree view problems.

Geographical Map Projection

Analogous pattern

Just like top view shows visible nodes from above, map projections show Earth's surface from a viewpoint, dealing with visibility and overlapping features.

Common Pitfalls

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

Wrong approach:

if (hdNodeMap.has(hd)) {
hdNodeMap.set(hd, node.val); // overwrites existing node
}

Correct approach:

if (!hdNodeMap.has(hd)) {
hdNodeMap.set(hd, node.val); // only set once
}

Root cause:

Misunderstanding that only the first node at each horizontal distance should be recorded for the top view.

#2 Using preorder traversal instead of level order traversal.

Wrong approach:

function preorderTopView(node, hd, map) {
if (!node) return;
if (!map.has(hd)) map.set(hd, node.val);
preorderTopView(node.left, hd - 1, map);
preorderTopView(node.right, hd + 1, map);
}

Correct approach:

Use a queue for level order traversal to ensure nodes are visited by depth:

function topView(root) {
// BFS with queue and map
}

Root cause:

Not realizing that preorder does not guarantee visiting nodes in order of depth, leading to incorrect top view.

#3 Printing top view nodes without sorting by horizontal distance.

Wrong approach:

for (const val of hdNodeMap.values()) {
console.log(val + ' -> ');
}

Correct approach:

for (let i = minHd; i <= maxHd; i++) {
if (hdNodeMap.has(i)) console.log(hdNodeMap.get(i) + ' -> ');
}

Root cause:

Ignoring the spatial order of nodes, which is essential to represent the top view correctly.

Key Takeaways

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

Horizontal distance is a key concept that assigns positions to nodes relative to the root, enabling grouping for the top view.

Level order traversal (BFS) is essential to visit nodes by depth, ensuring the topmost nodes are recorded first for each horizontal distance.

Only the first node encountered at each horizontal distance is included in the top view; later nodes at the same distance are ignored.

Printing the top view nodes in order from leftmost to rightmost horizontal distance accurately represents the tree's top view.