Bottom View of a Binary Tree

Assign the root horizontal distance hd = 0; its left child has hd minus 1 and right child hd plus 1. Run level-order BFS with queue entries containing node and hd. Store the latest value seen for each hd in a map. Because BFS processes shallower levels first, a later visit at the same hd is at least as deep; overwriting produces the bottom candidate, with traversal order providing the usual tie behavior for nodes at equal depth. To make depth ties explicit, store both depth and value and replace only when depth is greater or when a stated tie rule applies. Finally iterate horizontal distances in ascending order, using a sorted map or tracking minimum and maximum. Test a single node, nodes sharing a vertical line, a skewed tree, and equal-depth collisions. Traversal is O(n); sorted output costs O(k log k) for k horizontal distances, and map plus queue space is O(n).