Top View of Binary Tree

Given the root of a binary tree, return its top view from left to right.

The top view contains the nodes that are visible when the tree is observed from above. For every vertical position, only the node closest to the root is visible; nodes lying below it at the same position are hidden.

To identify vertical positions, a horizontal distance (hd) is assigned to every node. It represents how far a node lies horizontally from the root:

The root has hd = 0.
A left child has hd = parentHD - 1.
A right child has hd = parentHD + 1.

The visible node values must be returned from the smallest horizontal distance to the largest.

Example 1

Input: root = [1, 2, 3, null, 4, null, 5]

Output: [2, 1, 3, 5]

Explanation: Node 2 is visible at horizontal distance -1, node 1 at 0, node 3 at 1, and node 5 at 2. Node 4 lies below node 1 at horizontal distance 0, so it is hidden from the top view.

Example 2

Input: root = [1, 2, 3, 4, 5, 6, 7]

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

Explanation: The topmost nodes from the leftmost to the rightmost vertical line are 4, 2, 1, 3, 7. Nodes 5 and 6 lie below node 1 on the same vertical line and are therefore not visible from above.

Practice it by yourself before moving onto the solutionTry now

Brute Force Approach

Nodes lying on the same vertical line have the same horizontal distance (hd). Here, hd is used to group nodes belonging to the same vertical position.

For the top view, the node with the smallest level on each vertical line must be selected because it is closest to the root. Therefore, every node can be recorded along with its horizontal distance and level.

A traversal order can also be stored as a tie-breaker when multiple nodes appear at the same horizontal distance and level. After all nodes have been collected, the entries are sorted first by horizontal distance and then by level.

The first node appearing for every horizontal distance after sorting represents the topmost visible node.

This approach is straightforward, but sorting information for all N nodes introduces an additional O(N log N) cost.

Algorithm

Each node is traversed along with its horizontalDistance, level, and traversal order so that its vertical position and depth are recorded.
The root is assigned horizontal distance 0 and level 0. For every left child, the horizontal distance is decreased by 1, while for every right child, it is increased by 1.
All recorded entries are sorted first by horizontal distance and then by level, while traversal order is used to resolve ties.
For every horizontal distance, the first node appearing in the sorted sequence is selected because it has the minimum depth for that vertical line.
All remaining nodes having the same horizontal distance are ignored because they are hidden below the selected node.
The selected values are returned from the smallest horizontal distance to the largest.

Dry Run

Top View of Binary Tree Brute Force Approach Dry Run.png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int x) {
      val = x;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17private:
  struct Entry {
      int hd;
      int level;
      int order;
      int value;
  };
24
25public:
  // Finds the top view by storing
  // and sorting information for all nodes.
  vector<int> topView(TreeNode* root) {
      if (root == nullptr) {
          return {};
      }
32
      vector<Entry> nodes;
      queue<tuple<TreeNode*, int, int>> q;
35
      q.push({root, 0, 0});
37
      int order = 0;
39
      // Traverse the complete tree and store
      // horizontal distance, level, and order.
      while (!q.empty()) {
          auto [node, hd, level] = q.front();
          q.pop();
45
          nodes.push_back({
              hd,
              level,
              order++,
              node->val
          });
52
          if (node->left != nullptr) {
              q.push({
                  node->left,
                  hd - 1,
                  level + 1
              });
          }
60
          if (node->right != nullptr) {
              q.push({
                  node->right,
                  hd + 1,
                  level + 1
              });
          }
      }
69
      // Sorting places vertical lines from left
      // to right and shallower nodes first.
      sort(
          nodes.begin(),
          nodes.end(),
          [](const Entry& a, const Entry& b) {
              if (a.hd != b.hd) {
                  return a.hd < b.hd;
              }
79
              if (a.level != b.level) {
                  return a.level < b.level;
              }
83
              return a.order < b.order;
          }
      );
87
      vector<int> answer;
      int previousHD = INT_MIN;
90
      // The first node for each horizontal
      // distance is visible from the top.
      for (const Entry& entry : nodes) {
          if (entry.hd != previousHD) {
              answer.push_back(entry.value);
              previousHD = entry.hd;
          }
      }
99
      return answer;
  }
102};
103
104int main() {
  TreeNode* 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);
110
  Solution solution;
  vector<int> answer = solution.topView(root);
113
  for (int value : answer) {
      cout << value << " ";
  }
117
  return 0;
119}

Complexity Analysis

Time Complexity: O(N log N), where N is the number of nodes in the binary tree. All N nodes are recorded and then sorted.

Space Complexity: O(N), where N is the number of nodes in the binary tree. Information for every node may be stored before the answer is constructed.

Better Approach

Sorting information for every node is unnecessary because only the topmost node for each horizontal distance is required.

During DFS, two values are tracked:

hd represents the horizontal distance of the current node from the root and identifies its vertical line.
level represents the depth of the current node and determines how close it is to the root.

For every horizontal distance, an ordered map stores two pieces of information: the current topmost node value and its storedLevel. The storedLevel represents the smallest depth encountered so far for that horizontal distance.

If another node reaches the same horizontal distance at a greater level, it lies below the already stored node and cannot belong to the top view. A replacement is made only when a node is found at a smaller level.

Because an ordered map keeps ho

Algorithm

DFS is started from the root with horizontal distance 0 and level 0.
An ordered map is maintained in which every horizontal distance stores the smallest storedLevel encountered so far and its corresponding node value.
When a horizontal distance is encountered for the first time, the current node and its level are stored because it is currently the topmost known node on that vertical line.
If the same horizontal distance has already been recorded, its entry is replaced only when the current level is smaller than storedLevel.
The left subtree is explored with hd - 1, while the right subtree is explored with hd + 1, so their vertical positions remain correctly represented.
After the traversal is completed, the ordered map is read from the smallest horizontal distance to the largest to construct the top view.

Dry Run

Top View of Binary Tree Better Approach Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
8
  TreeNode(int x) {
      val = x;
      left = nullptr;
      right = nullptr;
  }
14};
15
16class Solution {
17private:
  // Stores the shallowest node
  // found for every horizontal distance.
  void dfs(
      TreeNode* node,
      int hd,
      int level,
      map<int, pair<int, int>>& topNodes
  ) {
      if (node == nullptr) {
          return;
      }
29
      auto it = topNodes.find(hd);
31
      // DFS may reach a deeper node first.
      // Keep only the smallest level for this hd.
      if (
          it == topNodes.end()
          || level < it->second.first
      ) {
          topNodes[hd] = {
              level,
              node->val
          };
      }
43
      dfs(
          node->left,
          hd - 1,
          level + 1,
          topNodes
      );
50
      dfs(
          node->right,
          hd + 1,
          level + 1,
          topNodes
      );
  }
58
59public:
  // Finds the top view using DFS
  // with level information.
  vector<int> topView(TreeNode* root) {
      if (root == nullptr) {
          return {};
      }
66
      map<int, pair<int, int>> topNodes;
68
      dfs(root, 0, 0, topNodes);
70
      vector<int> answer;
72
      // The ordered map already stores
      // horizontal distances left to right.
      for (auto& entry : topNodes) {
          answer.push_back(
              entry.second.second
          );
      }
80
      return answer;
  }
83};
84
85int main() {
  TreeNode* 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);
91
  Solution solution;
  vector<int> answer = solution.topView(root);
94
  for (int value : answer) {
      cout << value << " ";
  }
98
  return 0;
100}

Complexity Analysis

Time Complexity: O(N log N), where N is the number of nodes in the binary tree. Every node is visited once, and each ordered-map insertion or lookup can require O(log N) time.

Space Complexity: O(N), where N is the number of nodes in the binary tree. The ordered map may store information for multiple horizontal distances, while the recursion stack may also require up to O(N) space in the worst case.

Optimal Approach

For the top view, only the shallowest node at each horizontal distance is required.

BFS is well suited to this requirement because nodes are processed level by level. Therefore, the first node encountered at a particular hd is already the closest node to the root on that vertical line.

Here, hd identifies the vertical line of the current node. Once a value has been stored for an hd, later nodes encountered at the same position are deeper and are not allowed to replace it.

Two additional variables are maintained:

minHD stores the smallest horizontal distance encountered and identifies the leftmost visible vertical line.
maxHD stores the largest horizontal distance encountered and identifies the rightmost visible vertical line.

These boundaries allow the final answer to be collected directly from minHD to maxHD without sorting the horizontal distances afterward.

Algorithm

If the root is null, an empty result is returned because no node is visible.
The pair (root, 0) is inserted into a queue, where 0 represents the root's horizontal distance.
A map is maintained from horizontal distance to node value, while minHD and maxHD are maintained to record the leftmost and rightmost horizontal distances reached.
During BFS, a node value is stored only when its horizontal distance has not been recorded earlier, because the first node encountered by BFS is the shallowest node at that vertical position.
The left child is inserted with hd - 1 and the right child with hd + 1, while minHD and maxHD are updated whenever the horizontal range expands.
After BFS is completed, the stored values are collected from minHD through maxHD so that the result is produced from left to right.

Dry Run

Top View of Binary Tree Optimal Approach Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
5    int val;
6    TreeNode* left;
7    TreeNode* right;
8
9    TreeNode(int x) {
10        val = x;
11        left = nullptr;
12        right = nullptr;
13    }
14};
15
16class Solution {
17public:
18    // Finds the top view by recording
19    // the first node at every hd.
20    vector<int> topView(TreeNode* root) {
21        if (root == nullptr) {
22            return {};
23        }
24
25        unordered_map<int, int> topNode;
26        queue<pair<TreeNode*, int>> q;
27
28        q.push({root, 0});
29
30        int minHD = 0;
31        int maxHD = 0;
32
33        // BFS processes shallower nodes first.
34        // The first node at an hd is topmost.
35        while (!q.empty()) {
36            auto [node, hd] = q.front();
37            q.pop();
38
39            // Once an hd is recorded, deeper
40            // nodes at that hd stay hidden.
41            if (topNode.find(hd) == topNode.end()) {
42                topNode[hd] = node->val;
43            }
44
45            if (node->left != nullptr) {
46                int leftHD = hd - 1;
47
48                q.push({
49                    node->left,
50                    leftHD
51                });
52
53                minHD = min(minHD, leftHD);
54            }
55
56            if (node->right != nullptr) {
57                int rightHD = hd + 1;
58
59                q.push({
60                    node->right,
61                    rightHD
62                });
63
64                maxHD = max(maxHD, rightHD);
65            }
66        }
67
68        vector<int> answer;
69
70        // Read from minHD to maxHD
71        // to preserve left-to-right order.
72        for (int hd = minHD; hd <= maxHD; hd++) {
73            answer.push_back(topNode[hd]);
74        }
75
76        return answer;
77    }
78};
79
80int main() {
81    TreeNode* root = new TreeNode(1);
82    root->left = new TreeNode(2);
83    root->right = new TreeNode(3);
84    root->left->right = new TreeNode(4);
85    root->right->right = new TreeNode(5);
86
87    Solution solution;
88    vector<int> answer = solution.topView(root);
89
90    for (int value : answer) {
91        cout << value << " ";
92    }
93
94    return 0;
95}

Complexity Analysis

Time Complexity: O(N) on average, where N is the number of nodes in the binary tree. Every node is processed once, and hash-map operations require O(1) average time.

Space Complexity: O(N), where N is the number of nodes in the binary tree. The BFS queue and horizontal-distance map may together store information for up to all nodes.

FAQS

Q1. Why is horizontal distance needed for the Top View?

Horizontal distance identifies the vertical line on which a node lies. Since only one topmost node can be visible from each vertical line, horizontal distance allows competing nodes to be grouped correctly.

Q2. How is Top View different from Vertical Order Traversal?

Top View keeps only the shallowest visible node from each horizontal distance. Vertical Order Traversal can contain all nodes lying on the same vertical line.

Q3. Why can DFS not simply store the first node encountered at every horizontal distance?

DFS may reach a deeper node before visiting a shallower node from another subtree. Therefore, DFS must also track the level and keep the node having the smallest depth.

Q4. How is Top View different from Vertical Order Traversal?

Top View keeps only the topmost visible node from each horizontal distance. Vertical Order Traversal may include all nodes lying on the same vertical line.

Q5. What is the main difference between Top View and Bottom View?

For Top View, the first or shallowest node at each horizontal distance is retained. For Bottom View, deeper nodes at the same horizontal distance replace shallower ones.

Top View of Binary Tree

Example 1

Example 2

Brute Force Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Better Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Optimal Approach

Algorithm

Dry Run

Solution

Complexity Analysis

FAQS

Read Similar Blogs

Parent and Distance - Introduction

Check If a Binary Tree Is a Subtree of Another Tree

Count Nodes in a Complete Binary Tree