Algorithm/Insights
To solve this problem we use a simple idea of using level order traversal with slight modification. The modification is that while doing the level order traversal, we keep track of the horizontal distance(from the root node) of the current node being visited. During this level-order traversal, we update the treeMap(a modified hashMap which keeps entries sorted by key) with node's horizontal distance as key and value as current node's value if the node being visited is the bottommost node seen at its horizontal distance. And because we are doing a level order traversal starting from top-most level and ending at bottom-most level, all we need to do keep updating the treeMap with (nodeValue, horizontalDistance) at each node's visit. Notice that, if there are multiple nodes at the same horizontal distance, then bottom most node of these will overwrite the entry of other nodes in the viewMap.
The algorithm is as following -
1. Initialize viewMap to an empty treeMap.
2. Call fillUpViewMap function with arguments as (root = root, viewMap = viewMap)
3. If root is null, do nothing and return.
4. If root is not null then - (following steps basically do a level order traversal of the given tree)
4a. Add the tuple(currentNode = rootNode, horizontalDistance = 0) to the queue - 'nodeQueue'.
4b. while 'nodeQueue' is not empty
- remove first tuple(currentNode, horizontalDistance) from 'nodeQueue'
- update the viewMap with tuple (key = horizontalDistance, value = currentNode's value). If viewMap already contains an entry with 'horizontalDistance' as key, then we overwrite the previous entry with this current entry - (key = horizontalDistance, value = currentNode's value).
- if left child of currentNode is not null, then we add tuple(currentNode.left, horizontalDistance - 1) to 'nodeQueue'
- if right child of currentNode is not null, then we add tuple(currentNode.right, horizontalDistance + 1) to 'nodeQueue'
5. After completion of step #4, our viewMap is completely updated with keys(horizontal distance) and values(nodeValues) in sorted order of keys. All we need to do is print out the values in this viewMap to get the bottomView.
Please checkout code snippet and algorithm visualization section for more details of the algorithm.