Tree View Traversal: Top and Bottom

1. The Core Idea: Horizontal Distance

While left/right views only care about a node's level (its vertical position), top/bottom views also care about its horizontal position relative to the root. We can quantify this using a concept called horizontal distance (HD).

The rules are simple:

• The root node is at HD = 0.
• For any node at HD = x, its left child is at HD = x - 1.
• For any node at HD = x, its right child is at HD = x + 1.

This creates a system of vertical "lanes" or "lines" passing through the tree.

Our goal for both top and bottom views is to find one node for each horizontal distance. The question is, which one?

2. Finding the Top View of a Binary Tree

The top view consists of the nodes that are visible when looking at the tree from directly above. This means that for each horizontal distance, we want to select the highest node (i.e., the one with the smallest level number).

Since a Level-Order Traversal (BFS) naturally explores the tree from top to bottom, it's the perfect tool for this job. The first time we encounter a node at a new horizontal distance during our BFS, it is guaranteed to be the highest one at that HD.

The Algorithm

1. We'll use a Queue for our BFS. However, the queue can't just store nodes; it must also store their horizontal distance. So, we'll queue up pairs of (Node, horizontal_distance).
2. We'll use a Map to store our result. The map will associate each horizontal distance (the key) with the value of the first node we find at that HD (the value). A TreeMap is an excellent choice here because it automatically keeps the keys (the horizontal distances) sorted, which makes it trivial to build the final, ordered list of nodes from left to right.
3. Start the BFS by adding the (root, 0) pair to the queue.
4. In the BFS loop, dequeue a pair (currentNode, hd).
5. Check the map: If the map does not already contain the key hd, it means this is the first time we're visiting this horizontal line. We add the entry (hd, currentNode.data) to our map. If the key is already there, we do nothing, because we've already found a higher node at this same HD.
6. Enqueue the left child (if it exists) with hd - 1 and the right child (if it exists) with hd + 1.
7. After the BFS is complete, the values of the TreeMap will give the top view, sorted from left to right.

The following video from "take U forward" provides an excellent walkthrough of this exact logic.

Java Implementation for Top View

Here is a clean Java implementation based on the algorithm discussed. You'll notice it uses TreeMap to handle sorting the horizontal distances automatically.

• Time Complexity: $O(N)$, where N is the number of nodes, because we visit each node once in our traversal. The map operations (containsKey, put) take $O(\log K)$ time for a TreeMap where K is the number of unique horizontal distances (the width of the tree), but this is dominated by the $O(N)$ traversal.
• Space Complexity: $O(W)$, where W is the maximum width of the tree. This space is required for the queue and the map, both of which can hold up to W elements in the worst case (a complete binary tree).

3. Finding the Bottom View of a Binary Tree

The bottom view is what you'd see if you were looking up at the tree from below. For each horizontal distance, we want to select the lowest node. If two nodes are at the same lowest level for a given HD, we pick the one that comes later in the level-order traversal.

Happily, this requires only a tiny change to our top view algorithm.

The Algorithm (with a single change)

We still use BFS with a queue of (Node, horizontal_distance) pairs and a Map to store the result.

The only difference is in step 5:
5. In the BFS loop, dequeue a pair (currentNode, hd).
6. Unconditionally update the map: map.put(hd, currentNode.data).

Why does this work? Since BFS processes the tree level by level, the last time we call map.put(hd, ...) for any given hd, we are guaranteed to be at the lowest level containing that hd. This simple overwrite mechanic correctly identifies the bottom-most node for each vertical line.

Java Implementation for Bottom View

The code is almost identical to the top view solution, with just one line of logic changed.

import java.util.*;

// We can create a helper class for the pair, which is cleaner for interviews
class Pair {
    Node node;
    int hd; // Horizontal Distance

    Pair(Node node, int hd) {
        this.node = node;
        this.hd = hd;
    }
}

public class Solution {
    public ArrayList<Integer> bottomView(Node root) {
        ArrayList<Integer> ans = new ArrayList<>();
        if (root == null) return ans;

        // Use a TreeMap to store nodes sorted by horizontal distance
        Map<Integer, Integer> map = new TreeMap<>();
        Queue<Pair> q = new LinkedList<>();

        q.add(new Pair(root, 0));

        while (!q.isEmpty()) {
            Pair current = q.poll();
            Node node = current.node;
            int hd = current.hd;

            // THE ONLY CHANGE: Always update the map for the current HD.
            // The last node seen at this HD will be the one that remains.
            map.put(hd, node.data);

            if (node.left != null) {
                q.add(new Pair(node.left, hd - 1));
            }
            if (node.right != null) {
                q.add(new Pair(node.right, hd + 1));
            }
        }

        // The TreeMap's values are the bottom view, sorted by HD.
        for (int value : map.values()) {
            ans.add(value);
        }
        return ans;
    }
}

You can also refer to the GeeksForGeeks article on "Bottom View of a Binary Tree" (LINK) for another excellent explanation of this BFS-based approach.

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

Conclusion

In this lesson, we expanded our tree traversal toolkit to solve top and bottom view problems by introducing the concept of horizontal distance.

Key Takeaways:

• Top and bottom views require tracking nodes on a 2D grid defined by level (vertical) and horizontal distance.
• A Level-Order Traversal (BFS) is the most intuitive method because it processes nodes top-to-bottom.
• We use a queue of pairs (Node, horizontal_distance) to manage the traversal state.
• A Map<Integer, Integer> (ideally a TreeMap) stores the result, mapping horizontal distances to node values.
• For Top View: Only add a node to the map if its horizontal distance hasn't been seen before.
• For Bottom View: Always update the map with the current node's data for its horizontal distance. The last update for each distance "wins".

Preview of the Next Lesson:
We will shift our focus from "view" problems to problems about the relationships between nodes. In the next lesson, you'll learn how to find the Lowest Common Ancestor (LCA) of two nodes in a binary tree, a fundamental problem with very efficient and clever solutions.