DEV Community

Jaspreet singh
Jaspreet singh

Posted on

Bottom View of Binary Tree

#algorithms #coding #computerscience #interview
geeksforgeeks.org

Problem Statement

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

For every horizontal distance (HD), the bottom-most node should be included.

Brute Force Intuition

In an interview, you can explain it like this:

Compute the horizontal distance of every node and store all nodes belonging to that distance along with their levels. Finally, choose the deepest node for every horizontal distance.

This works but requires storing multiple nodes for each horizontal distance.

Complexity

  • Time Complexity: O(N log N)
  • Space Complexity: O(N)

Moving Towards the Optimal Approach

Notice that:

BFS

↓

Processes Nodes

Level by Level
Enter fullscreen mode Exit fullscreen mode

Unlike Top View,

we don't want the first node.

We always want the:

Latest Node
Enter fullscreen mode Exit fullscreen mode

encountered for every horizontal distance.

Since BFS visits deeper nodes later,

we simply overwrite the previous value.

Pattern Recognition

Whenever you see:

  • Bottom View
  • Top View
  • Vertical Traversal

Think:

Level Order Traversal + Horizontal Distance

Key Observation

Assign every node a:

Horizontal Distance (HD)
Enter fullscreen mode Exit fullscreen mode

Rules:

Root → 0

Left Child → HD - 1

Right Child → HD + 1
Enter fullscreen mode Exit fullscreen mode

Whenever we visit a node,

simply update:

map.put(hd, node.data);
Enter fullscreen mode Exit fullscreen mode

The last value stored for an HD becomes the bottom view.

Optimal Approach

Step 1

Perform BFS.

Queue stores:

(Node, HD)
Enter fullscreen mode Exit fullscreen mode

Step 2

Maintain:

TreeMap<Integer, Integer>
Enter fullscreen mode Exit fullscreen mode

Key:

Horizontal Distance
Enter fullscreen mode Exit fullscreen mode

Value:

Latest Node Value
Enter fullscreen mode Exit fullscreen mode

Step 3

For every node:

map.put(hd, node.data);
Enter fullscreen mode Exit fullscreen mode

Always overwrite.

Step 4

Traverse the TreeMap from left to right.

Optimal Java Solution 

class Pair {

    Node node;
    int hd;

    Pair(Node node, int hd) {

        this.node = node;
        this.hd = hd;
    }
}

class Solution {

    public ArrayList<Integer> bottomView(Node root) {

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

        if (root == null)
            return ans;

        Queue<Pair> q = new LinkedList<>();

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

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

        while (!q.isEmpty()) {

            Pair curr = q.poll();

            map.put(curr.hd, curr.node.data);

            if (curr.node.left != null)

                q.offer(new Pair(
                    curr.node.left,
                    curr.hd - 1));

            if (curr.node.right != null)

                q.offer(new Pair(
                    curr.node.right,
                    curr.hd + 1));
        }

        ans.addAll(map.values());

        return ans;
    }
}
Enter fullscreen mode Exit fullscreen mode

Dry Run 

          1
        /   \
       2     3
      / \   / \
     4   5 6   7
Enter fullscreen mode Exit fullscreen mode

Horizontal Distances:

4 → -2

2 → -1

1 → 0

3 → +1

7 → +2
Enter fullscreen mode Exit fullscreen mode

While traversing:

HD = 0

1

↓

5

↓

6
Enter fullscreen mode Exit fullscreen mode

Latest node:

6
Enter fullscreen mode Exit fullscreen mode

Final Bottom View:

[4,2,6,3,7]
Enter fullscreen mode Exit fullscreen mode

Why BFS Works?

BFS visits nodes level by level.

For each horizontal distance,

deeper nodes are processed later.

By continuously overwriting the value for each HD,

the last stored node naturally becomes the bottom-most visible node.

Complexity Analysis

Metric Complexity
Time Complexity O(N log N)
Space Complexity O(N)

log N comes from inserting keys into the TreeMap.

Interview One-Liner

Perform a level-order traversal while tracking horizontal distances and overwrite the node value for each distance so the last node becomes the bottom view.

Pattern Learned 

BFS

↓

Horizontal Distance

↓

Overwrite Node

↓

Bottom View
Enter fullscreen mode Exit fullscreen mode

Similar Problems

  • Bottom View of Binary Tree
  • Top View of Binary Tree
  • Vertical Order Traversal
  • Vertical Sum
  • Left View
  • Right View

Memory Trick

Think:

Horizontal Distance

↓

Always Update

↓

Last Node Wins
Enter fullscreen mode Exit fullscreen mode

Mental Model 

Queue

↓

(Node, HD)

↓

Overwrite Map

↓

Answer
Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

"Bottom View of Binary Tree"

your brain should immediately think:

BFS + Horizontal Distance + Overwrite Every Time

Top comments (0)