Top View of Binary Tree
https://workat.tech/problem-solving/practice/top-view-binary-tree
There are different ways to look at a binary tree. The top view of a binary tree contains the set of nodes that will be visible if you look at the binary tree from the top.
Given the root node of a binary tree, return an array containing the node elements in the top view, from left to right.
Note: The first level is traversed left to right.
Testing
Input Format
The first line contains an integer T denoting the number of test cases.
For each test case, the input has 2 lines:
- The first line contains an integer n denoting the number of nodes in the tree (including the NULL nodes).
- The second line contains n space-separated integers that will form the binary tree. The integers follow level order traversal of the tree where -1 indicates a NULL node.
Output Format
For each test case, the output contains a line with space-separated integers representing the top view of the binary tree.
Sample Input
5
7
1 2 -1 4 -1 5 6
3
6 -1 4
7
8 -1 9 -1 10 11 12
5
28 14 11 -1 48
1
6Expected Output
5 4 2 1
6 4
8 9 10 12
14 28 11
61 <= T <= 101 <= n <= 1051 <= node value <= 106
Intuition
At each column position, the first node encountered in a level order traversal is the top view
Track node val at each col in a HashMap<Integer, Integer>
If col is not present, add the first entry, also update min col, max col
Use Q based BFS
Store a Pair Node
Pair(TreeNode, col)
store left child with col - 1, right child with col + 1
Use min col, max col to iterate map in the end, avoids the need for TreeMap or additional sorting
---
Time Complexity - O(N)
Space Complexity - O(N)
---
Related problems
---
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| /* This is the Node class definition | |
| class Node { | |
| public Node left; | |
| public Node right; | |
| public int data; | |
| public Node(int data) { | |
| this.data = data; | |
| } | |
| } | |
| */ | |
| class Pair { | |
| Node node; | |
| int col; | |
| Pair(Node n, int c) { | |
| node = n; | |
| col = c; | |
| } | |
| } | |
| int[] topView(Node root) { | |
| if (root == null) { | |
| return new int[0]; | |
| } | |
| Queue<Pair> q = new LinkedList<Pair>(); | |
| q.offer(new Pair(root, 0)); | |
| Map<Integer, Integer> map = new HashMap<Integer, Integer>(); | |
| int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; | |
| while (!q.isEmpty()) { | |
| Pair pair = q.poll(); | |
| if (!map.containsKey(pair.col)) { | |
| map.put(pair.col, pair.node.data); | |
| min = Math.min(min, pair.col); | |
| max = Math.max(max, pair.col); | |
| } | |
| if (pair.node.left != null) { | |
| q.offer(new Pair(pair.node.left, pair.col - 1)); | |
| } | |
| if (pair.node.right != null) { | |
| q.offer(new Pair(pair.node.right, pair.col + 1)); | |
| } | |
| } | |
| int[] ans = new int[map.size()]; | |
| for (int i = min, j = 0; i <= max; i++, j++) { | |
| ans[j] = map.get(i); | |
| } | |
| return ans; | |
| } | |
| } |
