L22. Top View of Binary Tree | C++ | Java

Finding the top view of a binary tree means determining the sequence of nodes visible when looking straight down at the tree from above, flattened into a 1D perspective from left to right. This comprehensive guide covers the vertical line coordinate system, level-order traversal mechanics, data structure selection criteria (std::map), and full implementations in both C++ and Java.

1. Why Do We Need This? (Problem Statement & Status Quo)

When exploring binary trees, basic traversals (preorder, inorder, postorder, and standard level-order) visit every node systematically based on depth or hierarchy. However, spatial geometry problems—such as the Top View, Bottom View, and Vertical Order Traversal—require a coordinate-based mapping system.

• The Objective: Given the root of a binary tree, return an array/list containing the node values visible from the topmost vantage point, ordered horizontally from leftmost coordinate to rightmost coordinate.
• The Core Challenge: Nodes overlap vertically. If multiple nodes share the exact same horizontal position (column), only the topmost node (the one encountered first along that vertical line from above) should be added to the result.

2. Core Mental Model: The Vertical Line Coordinate System

To solve this, we adapt the vertical line concept from vertical order traversal. We assign an integer coordinate (line) to every node in the binary tree:

• Root Node: Assigned a baseline coordinate of line = 0.
• Moving Left: Subtract $1$ from the current line (line - 1).
• Moving Right: Add $1$ to the current line (line + 1).

Real-Life Analogy: Looking Down From a Rooftop

Imagine standing directly above a binary tree on a high rooftop looking straight down with parallel vertical laser beams slicing through every column:

• Every column represents a specific line index (e.g., -2, -1, 0, 1, 2).
• Nodes positioned directly underneath each other share the same column coordinate.
• The Top View consists strictly of the very first node hit by your line of sight in each column as you scan from left to right.

3. Naive vs. Better Approach: Why Level-Order Beats Recursion

You might wonder: Can we solve this using standard recursive DFS traversals (like Inorder, Preorder, or Postorder)?

• Why Recursion Fails Directly: If you use a simple recursive inorder traversal, you might visit a deeper node (e.g., node 6 at line -1) before visiting a shallower node (e.g., node 3 at line -1).
• The Fix for Recursion (Unnecessary Complexity): To make recursion work for top views, you would have to track both the horizontal line and the vertical level (height), updating the map only if a node has a strictly smaller level than the previously stored node at that line.
• The Optimal Approach (Level-Order Traversal): Using Breadth-First Search (BFS) / Level-Order Traversal guarantees that nodes closer to the root are visited before nodes deeper down. Therefore, the very first time we encounter any given line coordinate during a level-order traversal, that node is guaranteed to be the topmost visible node!

4. Step-by-Step Data Structure Requirements

To implement the level-order traversal with line tracking, we need two core data structures:

1. A Queue (BFS Queue): Stores pairs containing the tree TreeNode and its corresponding integer line coordinate. This ensures we process nodes level by level from top to bottom.
2. A Sorted Map (std::map in C++ / TreeMap in Java): Stores key-value pairs of (line -> node_val).
   • Crucial Rule: You must use a sorted map, never an unordered hash map. An ordered map automatically sorts keys in ascending order (from leftmost negative lines like -2, -1 up to positive lines like 0, 1, 2), which allows us to extract the final top view from left to right effortlessly.

5. Complete Flow Walkthrough

Let's trace how the algorithm processes a binary tree step-by-step.

Sample Binary Tree Layout

          1 (line 0)
        /   \
       2     3 (line 1)
   (line -1) / \
      /     5   7 (line 2)
     4     (line 0)
(line -2)  /
          6
      (line -1)

Trace Table of Level-Order Processing

After completing the queue traversal, iterating through the sorted map keys gives us our final Top View sequence from left to right:

[4, 2, 1, 3, 7]

6. Production-Ready Code Implementations

Below are the complete, robust implementations in C++ and Java.

C++ Implementation

#include <iostream>
#include <vector>
#include <queue>
#include <map>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    std::vector<int> topView(TreeNode* root) {
        std::vector<int> ans;
        if (root == nullptr) {
            return ans;
        }
        
        // Map to store the first node at each vertical line (line -> node->val)
        // std::map keeps keys sorted automatically
        std::map<int, int> topLineMap;
        
        // Queue stores a pair of {TreeNode*, line_number}
        std::queue<std::pair<TreeNode*, int>> q;
        
        q.push({root, 0});
        
        while (!q.empty()) {
            auto it = q.front();
            q.pop();
            
            TreeNode* node = it.first;
            int line = it.second;
            
            // If this line hasn't been visited yet, record the node's value
            if (topLineMap.find(line) == topLineMap.end()) {
                topLineMap[line] = node->val;
            }
            
            // Traverse left child (line - 1)
            if (node->left != nullptr) {
                q.push({node->left, line - 1});
            }
            
            // Traverse right child (line + 1)
            if (node->right != nullptr) {
                q.push({node->right, line + 1});
            }
        }
        
        // Extract values from the sorted map into the result vector
        for (auto pair : topLineMap) {
            ans.push_back(pair.second);
        }
        
        return ans;
    }
};

Java Implementation

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

// Helper class to bundle a Node with its horizontal line coordinate
class Tuple {
    TreeNode node;
    int line;
    
    Tuple(TreeNode node, int line) {
        this.node = node;
        this.line = line;
    }
}

class Solution {
    public List<Integer> topView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        
        // TreeMap stores sorted keys (line -> node.val)
        Map<Integer, Integer> topLineMap = new TreeMap<>();
        
        // Queue for BFS traversal holding Tuple objects
        Queue<Tuple> queue = new LinkedList<>();
        queue.offer(new Tuple(root, 0));
        
        while (!queue.isEmpty()) {
            Tuple current = queue.poll();
            TreeNode node = current.node;
            int line = current.line;
            
            // If the line is not present in the map, add it
            if (!topLineMap.containsKey(line)) {
                topLineMap.put(line, node.val);
            }
            
            // Push left child with line - 1
            if (node.left != null) {
                queue.offer(new Tuple(node.left, line - 1));
            }
            
            // Push right child with line + 1
            if (node.right != null) {
                queue.offer(new Tuple(node.right, line + 1));
            }
        }
        
        // Extract values from the sorted TreeMap
        for (int value : topLineMap.values()) {
            ans.add(value);
        }
        
        return ans;
    }
}

7. Complexity Analysis

• Time Complexity: $\mathcal{O}(N \log N)$, where $N$ is the total number of nodes in the binary tree. Every node is visited once during the queue traversal ($\mathcal{O}(N)$), and inserting each node's coordinate into a self-balancing binary search tree map (std::map / TreeMap) takes logarithmic time $\mathcal{O}(\log N)$ per insertion. (Note: If implemented with a hash map followed by sorting keys, it simplifies to $\mathcal{O}(N \log K)$ where $K$ is the number of vertical lines).
• Space Complexity: $\mathcal{O}(N)$ for storing nodes in the BFS queue (proportional to the maximum tree width at any given level) and the map data structures (std::map / TreeMap).

Summary and Key Takeaways

• Geometric Mapping: Spatial binary tree problems like the Top View rely on assigning relative horizontal coordinate lines (-1, 0, +1) during traversal.
• First-Come, First-Seen Rule: In a top-down view, the first node encountered on any specific vertical line is the only one visible from above.
• Level-Order Superiority: Breadth-First Search (BFS) naturally guarantees that shallower nodes are processed before deeper nodes, eliminating complex depth-checking logic required by recursive DFS approaches.
• Mandatory Sorted Maps: Always use ordered map structures (std::map in C++, TreeMap in Java) rather than unordered hash maps to ensure keys are automatically sorted from leftmost to rightmost columns.
• Queue Pair Pattern: Encapsulate both the tree node reference and its line coordinate into a queue pair or custom Tuple object during level-order iterations.
• Time and Space Efficiency: Achieves optimal $\mathcal{O}(N)$ traversal with clean linear storage scaling directly with tree depth and width.