Top View of Binary Tree in DSA Javascript - 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 the first node you see at each horizontal position. This view helps us understand the structure of the tree from a different angle than the usual left or right views.

Why it matters

Without the concept of top view, we would miss an important perspective of the tree's shape and structure. It helps in problems where we want to see which nodes are not hidden behind others when viewed from the top. This is useful in graphical representations, network routing, and understanding hierarchical data.

Where it fits

Before learning top view, you should understand binary trees, tree traversal methods, and the concept of horizontal distance in trees. After mastering top view, you can explore other views like bottom view, left view, right view, and vertical order traversal.

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 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, hiding the shorter ones behind it.

          (root)
           │
   ┌───────┴───────┐
 (left)          (right)

Horizontal distances:
Left nodes: negative distances
Root: zero
Right nodes: positive distances

Top view picks first node at each horizontal distance.

Build-Up - 7 Steps

1

Foundation

Understanding Binary Trees Basics

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

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 visualize and traverse a binary tree starting from the root.

Understanding the basic structure of binary trees is essential before exploring any special 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 when viewed from top.

Result

Each node has a horizontal distance value that helps identify its position horizontally.

Knowing horizontal distance allows us to group nodes by their position, 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 breadth-first (level order) traversal combined with horizontal distance to find top view nodes.

Traverse the tree level by level. For each node, record its horizontal distance. Keep track of the first node encountered at each horizontal distance.

Result

You get a map of horizontal distances to the first nodes seen at those distances.

Level order traversal ensures nodes closer to the root are processed first, which is why the first node at each horizontal distance is the top view node.

4

Intermediate

Using a Map to Store Top View Nodes

🤔Before reading on: Will updating the node at a horizontal distance every time you see a new node give the correct top view? Commit to yes or no.

Concept: Store nodes in a map keyed by horizontal distance, but only add the first node encountered at each distance.

When visiting nodes in level order, check if the horizontal distance is already in the map. If not, add the node. If yes, skip it.

Result

The map contains only the topmost nodes for each horizontal distance.

Preventing overwriting ensures only the top view nodes remain, reflecting the nodes visible from above.

5

Intermediate

Extracting and Printing the Top View

Concept: Sort the map keys and print nodes in order to show the top view from left to right.

After traversal, sort horizontal distances from smallest to largest. Print the corresponding nodes in this order to display the top view.

Result

A sequence of node values representing the top view from leftmost to rightmost.

Sorting horizontal distances aligns the output with the natural left-to-right view seen from above.

6

Advanced

Complete JavaScript Implementation

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

Concept: Implement the top view algorithm in JavaScript using a queue and a map.

```javascript class Node { constructor(data) { this.data = data; this.left = null; this.right = null; } } function topView(root) { if (!root) return []; const queue = []; 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.data); } if (node.left) { queue.push({ node: node.left, hd: hd - 1 }); if (hd - 1 < minHd) minHd = hd - 1; } if (node.right) { queue.push({ node: node.right, hd: hd + 1 }); if (hd + 1 > maxHd) maxHd = hd + 1; } } const result = []; for (let i = minHd; i <= maxHd; i++) { if (hdNodeMap.has(i)) { result.push(hdNodeMap.get(i)); } } return result; } // Example usage: 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); console.log(topView(root)); ```

Result

[2, 1, 3, 6]

Combining queue and map with horizontal distance tracking produces an efficient and clear solution for top view.

7

Expert

Handling Edge Cases and Optimizations

🤔Before reading on: Should nodes at the same horizontal distance but different depths always show the topmost node? Commit to yes or no.

Concept: Understand how to handle nodes overlapping in horizontal distance and optimize space/time complexity.

Nodes at the same horizontal distance but deeper levels are hidden in top view. Using level order traversal ensures the first node at each horizontal distance is the topmost. Optimizations include using a balanced tree or pruning unnecessary branches early.

Result

Correct top view even with complex trees and improved performance in large trees.

Knowing traversal order and node depth relationship prevents errors in top view and helps optimize for large data.

Under the Hood

The algorithm uses a breadth-first search (level order traversal) to visit nodes level by level. Each node is tagged with a horizontal distance relative to the root. A map stores the first node encountered at each horizontal distance. Because level order visits nodes top-down, the first node at a horizontal distance is the visible top node. Later nodes at the same horizontal distance but lower levels are ignored.

Why designed this way?

This approach ensures the top view reflects the nodes visible from above without complex backtracking. Alternatives like depth-first search fail because they may visit deeper nodes before shallower ones, causing incorrect top view. The map and queue combination balances simplicity and correctness.

┌───────────────┐
│   Start root  │
└──────┬────────┘
       │ hd=0
       ▼
┌───────────────┐
│ Enqueue root  │
└──────┬────────┘
       │
       ▼
┌─────────────────────────────┐
│ While queue not empty:       │
│  Dequeue node and hd         │
│  If hd not in map:           │
│    Add node to map           │
│  Enqueue left child hd-1     │
│  Enqueue right child hd+1    │
└─────────────┬───────────────┘
              │
              ▼
┌─────────────────────────────┐
│ After traversal:             │
│  Sort map keys (hd)          │
│  Output nodes in order       │
└─────────────────────────────┘

Myth Busters - 3 Common Misconceptions

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

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 hidden nodes behind others, breaking the concept of 'view from above' and causing incorrect results.

Quick: Can a depth-first traversal correctly find the top view without extra checks? Commit to yes or no.

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

Reality: Depth-first traversal may visit deeper nodes before shallower ones, causing incorrect top view unless additional logic is added.

Why it matters: Using depth-first without care can lead to wrong nodes being chosen for the top view, confusing the output.

Quick: Is horizontal distance the same as node depth? Commit to yes or no.

Common Belief: Horizontal distance and node depth are the same or interchangeable.

Reality: Horizontal distance measures left-right position relative to root; depth measures vertical level from root. They are different and both needed.

Why it matters: Confusing these leads to wrong grouping of nodes and incorrect top view calculation.

Expert Zone

1

The order of node insertion in the queue affects which node is recorded first at a horizontal distance when multiple nodes share the same horizontal distance and depth.

2

In trees with overlapping nodes at the same horizontal distance and depth, the left child is processed before the right child, influencing the top view result.

3

Optimizing memory by using a balanced tree or pruning can reduce the queue size and improve performance in very large trees.

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 engines to determine visible elements, in network routing to visualize hierarchical connections, and in coding interviews to test understanding of tree traversal and mapping techniques.

Connections

Vertical Order Traversal

Builds-on horizontal distance concept but includes all nodes at each horizontal distance sorted by depth.

Understanding top view helps grasp vertical order traversal since both use horizontal distances but differ in node selection.

Breadth-First Search (BFS)

Top view algorithm relies on BFS to visit nodes level by level ensuring correct node order.

Mastering BFS is key to implementing top view correctly and efficiently.

Computer Graphics Visibility

Top view relates to visibility determination in graphics where only front-most objects are rendered.

Knowing top view algorithms aids understanding how computers decide which objects to show when rendering scenes.

Common Pitfalls

#1 Overwriting nodes at the same horizontal distance instead of keeping the first.

Wrong approach:

if (hdNodeMap.has(hd)) {
hdNodeMap.set(hd, node.data);
}

Correct approach:

if (!hdNodeMap.has(hd)) {
hdNodeMap.set(hd, node.data);
}

Root cause:

Misunderstanding that the top view requires the first node at each horizontal distance, not the last.

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

Wrong approach:

function dfs(node, hd) {
if (!node) return;
hdNodeMap.set(hd, node.data);
dfs(node.left, hd - 1);
dfs(node.right, hd + 1);
}

Correct approach:

Use level order traversal with queue to ensure nodes are processed top-down and left-right.

Root cause:

Assuming any traversal order works without considering node depth and order of visitation.

#3 Confusing horizontal distance with depth and using only one to decide visibility.

Wrong approach:

Assigning hd = depth and ignoring left/right position.

Correct approach:

Assign hd based on left/right moves from root: left child hd-1, right child hd+1.

Root cause:

Mixing vertical and horizontal positioning concepts leads to wrong node grouping.

Key Takeaways

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

Horizontal distance is a key concept that measures left-right position relative to the root, distinct from node depth.

Level order traversal combined with horizontal distance tracking ensures correct identification of top view nodes.

Using a map to store the first node at each horizontal distance prevents overwriting and preserves the top view.

Understanding top view helps in graphical rendering, network visualization, and prepares for more complex tree views.

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 the right side

D. Nodes visible when the tree is viewed from above

Solution

1. Step 1: Understand the top view concept

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

2. Step 2: Compare with other views

   Left or right views show nodes from sides, and leaf nodes are only the bottom nodes.

3. Final Answer:

   Nodes visible when the tree is viewed from above -> Option D

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 JavaScript data structure is best suited to store nodes by their horizontal distance when computing the top view of a binary tree?

easy

A. Set

B. Array

C. Map

D. Stack

Solution

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

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

2. Step 2: Choose the best data structure

   A Map allows storing key-value pairs with efficient lookup and insertion.

3. Final Answer:

   Map -> Option C

4. Quick Check:

   Map stores horizontal distance keys [OK]

Hint: Use Map for key-value horizontal distance storage [OK]

Common Mistakes:

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

3. What is the output of the following code snippet that prints the top view of the binary tree?

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

function topView(root) {
  if (!root) return [];
  const map = new Map();
  const queue = [{ node: root, hd: 0 }];
  while (queue.length) {
    const { node, hd } = queue.shift();
    if (!map.has(hd)) map.set(hd, node.data);
    if (node.left) queue.push({ node: node.left, hd: hd - 1 });
    if (node.right) queue.push({ node: node.right, hd: hd + 1 });
  }
  return [...map.entries()]
    .sort((a, b) => a[0] - b[0])
    .map(entry => entry[1]);
}

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

console.log(topView(root));

medium

A. [2, 1, 3, 5]

B. [2, 1, 3]

C. [2, 1, 4, 3, 5]

D. [1, 2, 3, 4, 5]

Solution

1. Step 1: Traverse the tree with horizontal distances

   Start at root (1) with hd=0, add left child (2) hd=-1, right child (3) hd=1, then 4 at hd=0 (ignored since hd=0 exists), 5 at hd=2.

2. Step 2: Collect first nodes at each horizontal distance

   Map stores hd:-1=2, hd:0=1, hd:1=3, hd:2=5. Sorted by hd: -1,0,1,2 gives [2,1,3,5].

3. Final Answer:

   [2, 1, 3, 5] -> Option A

4. Quick Check:

   Top view nodes by hd = [2,1,3,5] [OK]

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

Common Mistakes:

• Including nodes hidden behind others at same hd
• Not sorting by horizontal distance before output
• Adding nodes multiple times for same hd

4. Identify the bug in this top view function and select the correct fix:

function topView(root) {
  if (!root) return [];
  const map = new Map();
  const queue = [{ node: root, hd: 0 }];
  while (queue.length) {
    const { node, hd } = queue.pop();
    if (!map.has(hd)) map.set(hd, node.data);
    if (node.left) queue.push({ node: node.left, hd: hd - 1 });
    if (node.right) queue.push({ node: node.right, hd: hd + 1 });
  }
  return [...map.entries()]
    .sort((a, b) => a[0] - b[0])
    .map(entry => entry[1]);
}

medium

A. Replace queue.pop() with queue.shift() to process nodes in correct order

B. Change map to a Set to avoid duplicate nodes

C. Remove sorting before returning the result

D. Add a visited set to avoid infinite loops

Solution

1. Step 1: Understand queue usage in BFS

   Using queue.pop() removes last element, making it a stack (DFS), not BFS. BFS requires queue.shift() to process nodes in FIFO order.

2. Step 2: Fix the traversal order

   Replacing pop() with shift() ensures nodes are processed level by level, correctly capturing top view nodes.

3. Final Answer:

   Replace queue.pop() with queue.shift() to process nodes in correct order -> Option A

4. Quick Check:

   BFS needs shift(), not pop() [OK]

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

Common Mistakes:

• Using pop() causing wrong traversal order
• Using Set instead of Map losing key-value pairs
• Skipping sorting which orders output incorrectly

5. Given a binary tree where multiple nodes share the same horizontal distance and level, how should the top view algorithm decide which node to include in the output?

hard

A. Include the node that appears last in level order traversal at that horizontal distance

B. Include the node that appears first in level order traversal at that horizontal distance

C. Include the node with the maximum value at that horizontal distance

D. Include all nodes at that horizontal distance

Solution

1. Step 1: Understand node conflicts at same horizontal distance and level

   When nodes share horizontal distance and level, top view includes the first encountered node in level order (BFS) traversal.

2. Step 2: Reason why first node is chosen

   Because BFS visits nodes level by level from left to right, the first node at that horizontal distance is visible from top.

3. Final Answer:

   Include the node that appears first in level order traversal at that horizontal distance -> Option B

4. Quick Check:

   Top view = first node at hd in BFS order [OK]

Hint: Pick first node at horizontal distance in BFS [OK]

Common Mistakes:

• Choosing node by max value instead of order
• Including all nodes causing duplicates
• Choosing last node instead of first