Top View of Binary Tree in DSA C++

Mental Model

The top view of a binary tree shows the nodes visible when looking 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 trees because others block your view behind them.

       1
      / \
     2   3
      \   \
       4   5

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

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 \ \ 4 5

Goal: Print nodes visible from the top view: nodes that appear first at each horizontal distance from root.

Step 1: Start BFS from root (1) at horizontal distance (hd) = 0

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

Why: We begin from root to explore all nodes level by level with their horizontal distances

Step 2: Dequeue (1, hd=0), add 1 to top view map at hd=0

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

Why: First node at hd=0 is 1, so it is visible from top

Step 3: Dequeue (2, hd=-1), add 2 to top view map at hd=-1

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

Why: First node at hd=-1 is 2, so it is visible from top

Step 4: Dequeue (3, hd=1), add 3 to top view map at hd=1

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

Why: First node at hd=1 is 3, so it is visible from top

Step 5: Dequeue (4, hd=0), hd=0 already has node 1, so skip adding 4

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

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

Step 6: Dequeue (5, hd=2), add 5 to top view map at hd=2

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

Why: First node at hd=2 is 5, so it is visible from top

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <queue>
#include <map>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

void topView(Node* root) {
    if (!root) return;
    // Map to store first node at each horizontal distance
    map<int, int> top_nodes;
    // Queue stores pairs of node and its horizontal distance
    queue<pair<Node*, int>> q;
    q.push({root, 0});

    while (!q.empty()) {
        auto [node, hd] = q.front();
        q.pop();

        // If hd not seen before, add node data
        if (top_nodes.find(hd) == top_nodes.end()) {
            top_nodes[hd] = node->data;
        }

        if (node->left) q.push({node->left, hd - 1});
        if (node->right) q.push({node->right, hd + 1});
    }

    // Print top view from leftmost to rightmost hd
    for (auto& [hd, val] : top_nodes) {
        cout << val << " -> ";
    }
    cout << "null" << endl;
}

int main() {
    Node* 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);

    topView(root);
    return 0;
}

q.push({root, 0});

Start BFS from root with horizontal distance 0

auto [node, hd] = q.front(); q.pop();

Dequeue current node and its horizontal distance

if (top_nodes.find(hd) == top_nodes.end()) { top_nodes[hd] = node->data; }

Add node data if this horizontal distance is seen first time

if (node->left) q.push({node->left, hd - 1}); if (node->right) q.push({node->right, hd + 1});

Add left and right children with updated horizontal distances

for (auto& [hd, val] : top_nodes) { cout << val << " -> "; } cout << "null" << endl;

Print nodes in order from leftmost to rightmost horizontal distance

Output

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

Complexity Analysis

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

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

vs Alternative: Naive approach might try vertical traversal multiple times causing higher complexity; BFS with map is efficient and clean

Edge Cases

Empty tree

Function returns without printing anything

DSA C++

if (!root) return;

Tree with single node

Prints that single node as top view

DSA C++

q.push({root, 0});

All nodes on one side (left or right)

Prints all nodes in order from top to bottom on that side

DSA C++

if (node->left) q.push({node->left, hd - 1});
if (node->right) q.push({node->right, hd + 1});

When to Use This Pattern

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

Common Mistakes

Mistake: Not tracking horizontal distance correctly causing wrong nodes in top view
Fix: Use a queue storing pairs of node and horizontal distance, update hd by -1 for left and +1 for right child

Mistake: Overwriting nodes in map for same horizontal distance
Fix: Only add node to map if horizontal distance is not already present

Summary

Shows nodes visible from above in a binary tree by tracking horizontal distances.

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

The key is to do a level order traversal while recording the first node at each horizontal distance.

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 meaning of top view

   The top view of a binary tree shows nodes that are visible when looking down vertically from above the tree.

2. Step 2: Compare with other views

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

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

2. Which C++ STL container is best suited to store nodes by their horizontal distance for top view calculation?

easy

A. std::map

B. std::stack

C. std::vector

D. std::queue

Solution

1. Step 1: Identify the need for horizontal distance mapping

   Top view requires storing nodes by their horizontal distance from root, which can be negative or positive keys.

2. Step 2: Choose container supporting key-value pairs with sorted keys

   std::map stores keys in sorted order and allows negative keys, unlike vector which uses indices starting at 0.

3. Final Answer:

   std::map -> Option A

4. Quick Check:

   Use map for horizontal distance keys [OK]

Hint: Use map to store nodes by horizontal distance [OK]

Common Mistakes:

• Using vector which can't handle negative keys
• Using stack or queue which don't map keys
• Not sorting nodes by horizontal distance

3. What is the output of the top view for the following binary tree?

        1
       / \
      2   3
       \   \
        4   5
         \   \
          6   7

medium

A. [2, 1, 3, 5, 7]

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

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

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

Solution

1. Step 1: Assign horizontal distances (HD) to nodes

   Root 1 has HD=0; left child 2 is HD=-1; right child 3 is HD=1; 4 is right of 2 so HD=0; 5 is right of 3 so HD=2; 6 is right of 4 so HD=1; 7 is right of 5 so HD=3.

2. Step 2: Select first node at each HD from top to bottom

   HD=-1: 2; HD=0: 1; HD=1: 3; HD=2: 5; HD=3: 7. Nodes 4 and 6 are hidden behind 1 and 3 respectively.

3. Final Answer:

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

4. Quick Check:

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

Hint: Pick first node at each horizontal distance [OK]

Common Mistakes:

• Including nodes hidden behind others at same HD
• Mixing order of nodes in output
• Ignoring horizontal distance calculation

4. Identify the error in this C++ snippet for top view calculation:

std::map topViewMap;
std::queue> q;
q.push({root, 0});
while(!q.empty()) {
  auto p = q.front(); q.pop();
  Node* node = p.first;
  int hd = p.second;
  if(topViewMap.find(hd) == topViewMap.end())
    topViewMap[hd] = node->data;
  if(node->left) q.push({node->left, hd - 1});
  if(node->right) q.push({node->right, hd + 1});
}

medium

A. Using std::map instead of unordered_map causes slower lookup

B. Incorrect horizontal distance update for left and right children

C. Not checking if node is nullptr before accessing node->left and node->right

D. Not clearing the queue before starting the loop

Solution

1. Step 1: Check node pointer usage inside loop

   The code accesses node->left and node->right without verifying if node is nullptr, which can cause runtime errors if node is null.

2. Step 2: Verify other parts of code

   Horizontal distances are updated correctly; queue is initialized properly; map choice is valid though unordered_map could be faster but not an error.

3. Final Answer:

   Not checking if node is nullptr before accessing node->left and node->right -> Option C

4. Quick Check:

   Always check node != nullptr before child access [OK]

Hint: Check node pointer before accessing children [OK]

Common Mistakes:

• Ignoring nullptr checks causing crashes
• Confusing horizontal distance updates
• Assuming map choice causes errors

5. Given a binary tree where multiple nodes share the same horizontal distance and level, which node should appear in the top view?

hard

A. The node with the maximum value at that horizontal distance

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

C. The node that appears last in level order traversal at that horizontal distance

D. The leftmost node at that horizontal distance regardless of level

Solution

1. Step 1: Understand top view node selection criteria

   Top view shows the first node encountered at each horizontal distance when traversing level by level (top to bottom, left to right).

2. Step 2: Clarify why first node in level order is chosen

   Because level order visits nodes by increasing depth, the first node at a horizontal distance is the topmost visible node.

3. Final Answer:

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

4. Quick Check:

   Top view = first node per horizontal distance in level order [OK]

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

Common Mistakes:

• Choosing node by max value instead of position
• Picking last node instead of first in level order
• Ignoring level order traversal importance