Prerequisites: Binary tree, BT traversal.
Problem: Given a binary tree, print the top view of the tree.
The top view of a binary tree is the set of nodes visible when the tree is viewed from the top.
It is defined as the nodes visible from the top along the vertical line passing through the
leftmost node to rightmost node of the tree.
Solution Approach: This can be solved using a level-order traversal (BFS) to traverse the tree and calculate the top view of the binary tree. We can use a map to store the first encountered node at each vertical level. The key idea is to traverse the tree level by level, and at each level, only consider the first encountered node for that vertical line.
Algorithm:
-
- Implement the topView() function that takes the root of the binary tree as its parameter.
-
- Initialize a map v to store the top view nodes with their vertical indices.
-
- Use a queue to perform level-order traversal.
-
- Enqueue the root along with its vertical index (initially 0) into the queue.
-
- While the queue is not empty, perform the following steps:
- Dequeue a node and its vertical index from the front of the queue.
- If the vertical index is not already present in the map, insert the node’s value into the map at that vertical index.
- Enqueue the left child (if it exists) with a decremented vertical index.
- Enqueue the right child (if it exists) with an incremented vertical index.
-
- The map now contains the top view nodes at each vertical level. Iterate through the map and print the values.
Time Complexity: O(NlogN), as we need to visit each node once and use an ordered map to store the nodes.
Space Complexity: O(N), as we need to store each node in a map.