Problem Statement

Given the root of a binary tree, return the top view of the binary tree.

Top view of a binary tree is the set of nodes visible when the tree is viewed from the top. Return nodes from the leftmost node to the rightmost node. Also if 2 nodes are outside the shadow of the tree and are at the same position then consider the left ones only(i.e. leftmost).

Examples

Example 1:

Input:
        1
       / \
      2   3
     / \   \
    4   5   6

Output: [4, 2, 1, 3, 6]


Explanation:
The horizontal distances for nodes are:
HD -2: Node 4
HD -1: Node 2
HD 0: Node 1
HD 1: Node 3
HD 2: Node 6
The topmost nodes visible are [4, 2, 1, 3, 6].

Example 2:

Input:
         1
        / \
       2   3
        \
         4
          \
           5
            \
             6

Output: [2, 1, 3 6]

Explanation:
The horizontal distances for nodes are:
HD -1: Node 2
HD 0: Node 1
HD 1: Node 3
HD 2: Node 6
The topmost nodes visible are [2, 1, 3, 6].

Different Approaches

1️⃣ Horizontal Distance Approach

The top view of a binary tree consists of the nodes visible when the tree is observed from the top. Nodes at the same horizontal distance (HD) from the root overlap, and only the topmost node (closest to the root in level order traversal) for each HD is visible.

Key Observations:

1. Horizontal Distance (HD):
   • Start with HD = 0 for the root.
   • Move left → Decrease HD by 1.
   • Move right → Increase HD by 1.
2. Top View Selection:
   • Use level order traversal (BFS) to process nodes in top-to-bottom order.
   • Track the first node encountered at each HD using a map or similar data structure.

Approach:

1. Level Order Traversal (BFS):
   • Traverse the tree using a queue. Each node is paired with its HD.
   • For every node, check if its HD is already in the map. If not, it becomes part of the top view.
2. Track Top Nodes by HD:
   • Use a map to store the first node encountered for each HD.
   • Keys in the map represent HDs, and values represent the node values.
3. Extract Results:
   • Traverse the map in ascending order of HD to get the top view.

Code:

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

// Definition for a binary tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<int> topView(TreeNode* root) {
    if (!root) return {};

    // Map: HD -> Node value
    map<int, int> topNodes;
    // Queue for BFS: (node, HD)
    queue<pair<TreeNode*, int>> q;

    q.push({root, 0}); // Root has HD = 0

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

        // If this HD is not yet seen, add it to the map
        if (topNodes.find(hd) == topNodes.end()) {
            topNodes[hd] = node->val;
        }

        // Traverse the left and right children
        if (node->left) {
            q.push({node->left, hd - 1});
        }
        if (node->right) {
            q.push({node->right, hd + 1});
        }
    }

    // Extract the top view from the map
    vector<int> result;
    for (auto& [hd, value] : topNodes) {
        result.push_back(value);
    }

    return result;
}

// Helper function for building tree (optional)
TreeNode* buildTree() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->left->right->right = new TreeNode(5);
    root->left->right->right->right = new TreeNode(6);
    return root;
}

// Main
int main() {
    TreeNode* root = buildTree();
    vector<int> result = topView(root);
    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity:
  • Traversal: Each node is visited once during BFS which takes O(N), where N is the number of nodes.
  • Map Operations: Insertion into the map is O(log K), where K is the number of unique Horizontal Distances. Since K ≤ N, this contribute O(N log N).
  • Overall: O(N log N)
• Space Complexity:
  • Map Storage: Stores O(K) Horizontal Distance entries, where K≤N, It takes O(N).
  • Queue Storage: Stores up to O(N), nodes in the BFS queue. It takes O(N).
  • Overall: O(N)