Bottom View of Binary Tree

Time: O(n)

Space: O(n)

Intuition

Level-order traversal with horizontal distance (HD): root=0, left child=HDâˆ’1, right child=HD+1. For each HD, the LAST node seen at that HD (deepest level) is the bottom view.

Algorithm

1BFS with (node, HD) pairs. HashMap: HD â†’ last seen node value.
2Process each (node, hd): map[hd] = node.val (overwrite â€” last wins).
3Enqueue (left, hdâˆ’1) and (right, hd+1) if non-null.
4Return map values sorted by HD.

Example Walkthrough

Input: Tree: 20(root), left=8[left=5,right=3], right=22[right=25], 3 has left=10,right=14

1.HD: 5â†’-2, 8â†’-1, 10â†’0, 20â†’0, 3â†’0, 14â†’1, 22â†’1, 25â†’2. Bottom: 5,10,3,14,25.

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

Common Pitfalls

•BFS ensures we process level by level â€” map[hd] is always overwritten by deeper nodes.

Bottom View of Binary Tree.java

Java

// Approach: BFS with horizontal distance tracking. For each node record its HD.
// The last node seen at each HD in level-order gives the bottom view.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    // Function to return a list containing the bottom view of the given tree.
    public ArrayList<Integer> bottomView(Node root) {
        Queue<Pair> q = new ArrayDeque<>();
        Map<Integer, Integer> map = new TreeMap<>();

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

        while (!q.isEmpty()) {
            Pair curr = q.poll();
            map.put(curr.hdist, curr.node.data);

            if (curr.node.left != null)
                q.add(new Pair(curr.hdist - 1, curr.node.left));

            if (curr.node.right != null)
                q.add(new Pair(curr.hdist + 1, curr.node.right));
        }

        ArrayList<Integer> ans = new ArrayList<>();

        for (Map.Entry<Integer, Integer> mp : map.entrySet())
            ans.add(mp.getValue());

        return ans;
    }
}

class Pair {
    int hdist;
    Node node;

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

class Node {
    int data; // data of the node
    int hd; // horizontal distance of the node
    Node left, right; // left and right references

    // Constructor of tree node
    public Node(int key) {
        data = key;
        hd = Integer.MAX_VALUE;
        left = right = null;
    }
}

// Version 2

class Solution1 {
    class Pair1 {
        Node node;
        int hd;

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

    public ArrayList<Integer> bottomView(Node root) {
        ArrayList<Integer> ans = new ArrayList<>();

        Queue<Pair1> q = new LinkedList<>();
        q.add(new Pair1(root, 0));

        TreeMap<Integer, Node> map = new TreeMap<>();

        while (!q.isEmpty()) {

            Pair1 curr = q.poll();
            map.put(curr.hd, curr.node);

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

        for (int ele : map.keySet())
            ans.add(map.get(ele).data);

        return ans;
    }
}

Was this solution helpful?