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.

top-view-binary-tree

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
6

Expected Output

5 4 2 1
6 4
8 9 10 12
14 28 11
6

1 <= T <= 10
1 <= n <= 105
1 <= 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
---