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.

Practice

1. What does the top view of a binary tree represent?

easy

A. Nodes visible when the tree is viewed from the right side

B. Nodes visible when the tree is viewed from the left side

C. Nodes visible when the tree is viewed from above

D. All leaf nodes of the tree

Solution

1. Step 1: Understand the top view concept

   The top view of a binary tree shows nodes visible from the top, ignoring nodes hidden behind others vertically.

2. Step 2: Compare with other views

   Left or right views show nodes from sides, and leaf nodes are only the bottom-most nodes, so they differ from top view.

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
• Thinking top view includes all leaf nodes
• Assuming top view shows all nodes

2. Which TypeScript data structure is best suited to store nodes with their horizontal distances while computing the top view of a binary tree?

easy

A. Map (key-value pairs)

B. Array

C. Set

D. Stack

Solution

1. Step 1: Identify the need for key-value storage

   We need to store nodes with their horizontal distances as keys and node values as values.

2. Step 2: Choose the appropriate data structure

   A Map allows storing keys (horizontal distances) with corresponding node values efficiently.

3. Final Answer:

   Map (key-value pairs) -> Option A

4. Quick Check:

   Use Map for horizontal distance to node mapping [OK]

Hint: Use Map to link horizontal distance and node [OK]

Common Mistakes:

• Using Array which is index-based, not key-based
• Using Set which stores unique values without keys
• Using Stack which is LIFO, not suitable here

3. Given the following TypeScript code snippet for top view, what will be the printed output?

class Node {
  constructor(public data: number, public left: Node | null = null, public right: Node | null = null) {}
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.right = new Node(4);
root.left.right.right = new Node(5);
root.left.right.right.right = new Node(6);

function topView(root: Node) {
  const map = new Map();
  const queue: Array<[Node, number]> = [[root, 0]];

  while (queue.length) {
    const [node, hd] = queue.shift()!;
    if (!map.has(hd)) {
      map.set(hd, node.data);
    }
    if (node.left) queue.push([node.left, hd - 1]);
    if (node.right) queue.push([node.right, hd + 1]);
  }

  const sortedKeys = Array.from(map.keys()).sort((a, b) => a - b);
  const result = sortedKeys.map(key => map.get(key));
  console.log(result);
}

topView(root);

medium

A. [1, 2, 3, 4, 5, 6]

B. [2, 4, 1, 3, 6]

C. [2, 1, 3]

D. [2, 1, 3, 6]

Solution

1. Step 1: Assign horizontal distances and track first nodes

   Root(1) at hd=0, left(2) at hd=-1, right(3) at hd=1. Next nodes 4 at hd=0 (ignored, already 1), 5 at hd=1 (ignored, already 3), 6 at hd=2 (new).

2. Step 2: Collect nodes in order of horizontal distance

   Sorted keys: -1, 0, 1, 2 with values 2, 1, 3, 6 respectively.

3. Final Answer:

   [2, 1, 3, 6] -> Option D

4. Quick Check:

   Top view nodes = [2, 1, 3, 6] [OK]

Hint: First node at each horizontal distance is in top view [OK]

Common Mistakes:

• Including nodes hidden behind others at same horizontal distance
• Not sorting horizontal distances before output
• Adding all nodes instead of first at each horizontal distance

4. Identify the bug in the following TypeScript code for top view of a binary tree:

function topView(root: Node) {
  const map = new Map();
  const queue: Array<[Node, number]> = [[root, 0]];

  while (queue.length) {
    const [node, hd] = queue.pop()!;
    if (!map.has(hd)) {
      map.set(hd, node.data);
    }
    if (node.left) queue.push([node.left, hd - 1]);
    if (node.right) queue.push([node.right, hd + 1]);
  }

  const sortedKeys = Array.from(map.keys()).sort((a, b) => a - b);
  const result = sortedKeys.map(key => map.get(key));
  console.log(result);
}

medium

A. Using queue.pop() instead of queue.shift() causes wrong traversal order

B. Not checking if root is null before processing

C. Not sorting the keys before printing result

D. Using Map instead of Set for horizontal distances

Solution

1. Step 1: Analyze queue operation impact

   Using pop() removes from end, making traversal depth-first instead of breadth-first, breaking horizontal distance order.

2. Step 2: Correct traversal method

   Using shift() removes from front, ensuring level order traversal needed for correct top view.

3. Final Answer:

   Using queue.pop() instead of queue.shift() causes wrong traversal order -> Option A

4. Quick Check:

   Use shift() for BFS queue [OK]

Hint: Use shift() for BFS queue, not pop() [OK]

Common Mistakes:

• Using pop() causing DFS instead of BFS
• Ignoring null root check (less critical here)
• Not sorting keys before output (code does sort)

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 all nodes at each horizontal distance and pick the last inserted node

B. Update the map only if the new node's value is smaller than the existing one at that horizontal distance

C. Ignore horizontal distance and print nodes in level order

D. Use a stack instead of a queue for traversal

Solution

1. Step 1: Understand the problem with duplicates

   When nodes share horizontal distance and level, default top view picks first encountered node, not necessarily smallest value.

2. Step 2: Modify map update condition

   Update the map only if the new node's value is smaller than the stored value for that horizontal distance to ensure smallest value is shown.

3. Final Answer:

   Update the map only if the new node's value is smaller than the existing one at that horizontal distance -> Option B

4. Quick Check:

   Keep smallest node value per horizontal distance [OK]

Hint: Update map only if new node value is smaller [OK]

Common Mistakes:

• Ignoring value comparison, keeping first node only
• Using stack breaks level order needed
• Storing all nodes wastes memory and complicates logic