Bottom View of a Binary Tree

Problem Statement

Given a binary tree, return the bottom view — the set of nodes visible when the tree is viewed from the bottom.

For each horizontal distance from the root, return the last node encountered during a level-order traversal. If two nodes are at the same horizontal distance and same level, the rightmost one is considered.

Horizontal distance rules:

• Root has horizontal distance 0
• Left child has horizontal distance parent - 1
• Right child has horizontal distance parent + 1

Constraints

• 1 <= number of nodes <= 10^5
• -1000 <= node.val <= 1000
• The tree can be skewed

Example

Input:

        20
       /  \
      8    22
     / \     \
    5   3     25
       / \
      10  14

Output: [5, 10, 3, 14, 25]

Explanation:

• HD -2: node 5
• HD -1: node 10 (below node 8)
• HD 0: node 3 (below node 20)
• HD 1: node 14 (below node 22)
• HD 2: node 25

Follow-ups

1. What's the difference between bottom view and top view? How does your approach change?
2. What if we want the leftmost node at each horizontal distance instead of the last in BFS?
3. Can you solve this without using a queue (DFS approach)? What are the trade-offs?
4. How would you handle very wide trees where horizontal distance can be very large?