Log inSign up
mediumgeeksforgeeksNot Started

Bottom View of Binary Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on geeksforgeeks
Lesson

Problem Statement

Given a binary tree, print the bottom view from left to right.

A node is included in bottom view if it can be seen when looking at the tree from the bottom. If there are multiple bottom-most nodes for a horizontal distance, the node that is generated later (the rightmost at that level in BFS traversal) should be chosen.

Example 1 · Example 1: Tree with Multiple Columns:

Input: root = [20, 8, 22, 5, 3, 4, 25, null, null, 10, 14] Tree: 20 / \ 8 22 / \ / \ 5 3 4 25 / \ 10 14
Output: [5, 10, 4, 14, 25]
Explanation: Horizontal distances: HD -2: 5; HD -1: 10; HD 0: 4 (overwrites 20, 3); HD 1: 14 (overwrites 22); HD 2: 25.

Example 2 · Example 2: Small Tree:

Input: root = [1, 2, 3] Tree: 1 / \ 2 3
Output: [2, 1, 3]
Explanation: HD -1: 2; HD 0: 1; HD 1: 3.

Constraints:

  • 1 <= Number of nodes <= 105
  • 1 <= Data of a node <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand horizontal distance indexing in binary trees.
  • See why BFS with unconditional overwrite yields the bottom view.
  • Optimize output generation by tracking minHD and maxHD bounds instead of sorting map keys.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • View of binary tree from the bottom.
  • Horizontal distance coordinate system.
  • Vertical column projection.

Algorithmic Decision Tree:

  • If root == null -> return [].
  • BFS queue stores {node, hd}.
  • For each node, map[hd] = node.val (unconditional overwrite).
  • Enqueue left child with hd - 1, right child with hd + 1.

Connected Patterns:

Top View of Binary TreeVertical Order Traversal of Binary TreeBinary Tree Right Side View

1. Recursive DFS with (Depth, HD) Tracking

Intuition

Since DFS can visit lower nodes on one branch before higher nodes on another branch, storing map[HD] requires also storing the depth. If current depth >= stored depth, overwrite map[HD] = {val, depth}.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Helper dfs(node, hd, depth, map).
  2. Step 2: If node == null return.
  3. Step 3: If hd not in map or depth >= map[hd].depth: map[hd] = {val: node.val, depth}.
  4. Step 4: Recurse dfs(node.left, hd - 1, depth + 1) and dfs(node.right, hd + 1, depth + 1).
  5. Step 5: Sort map by hd and return values.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void dfs(TreeNode* node, int hd, int depth, map<int, pair<int, int>>& m) {
10 if (!node) return;
11 if (m.find(hd) == m.end() || depth >= m[hd].second) {
12 m[hd] = {node->val, depth};
13 }
14 dfs(node->left, hd - 1, depth + 1, m);
15 dfs(node->right, hd + 1, depth + 1, m);
16 }
17 vector<int> bottomView(TreeNode* root) {
18 map<int, pair<int, int>> m;
19 dfs(root, 0, 0, m);
20 vector<int> res;
21 for (auto& p : m) res.push_back(p.second.first);
22 return res;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n log n) — DFS takes O(n); sorting keys takes O(w log w) <= O(n log n).
  • Space complexity: O(n) — Map stores entries for up to n nodes, plus O(h) recursion stack.

2. BFS with Ordered Map

Intuition

Level order traversal guarantees top-to-bottom processing. A C++ std::map or Java TreeMap keeps keys ordered by horizontal distance automatically.

When to apply: Standard interview approach using language-native ordered maps.

Algorithm

  1. Step 1: If root == null return [].
  2. Step 2: Queue q stores pairs (node, hd). Push (root, 0).
  3. Step 3: While q is not empty: pop (node, hd); map[hd] = node.val.
  4. Step 4: If left child exists, push (node.left, hd - 1). If right child exists, push (node.right, hd + 1).
  5. Step 5: Output all values in ordered map.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> bottomView(TreeNode* root) {
10 if (!root) return {};
11 map<int, int> m;
12 queue<pair<TreeNode*, int>> q;
13 q.push({root, 0});
14 while (!q.empty()) {
15 auto [node, hd] = q.front(); q.pop();
16 m[hd] = node->val;
17 if (node->left) q.push({node->left, hd - 1});
18 if (node->right) q.push({node->right, hd + 1});
19 }
20 vector<int> res;
21 for (auto& p : m) res.push_back(p.second);
22 return res;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n log w) — Each of the n nodes inserted into ordered map taking O(log w) per insertion.
  • Space complexity: O(n) — Queue and map store up to n elements.

3. BFS with Dynamic Min/Max Bounds (Strict O(n))

Intuition

By tracking minHD = min(minHD, hd) and maxHD = max(maxHD, hd) during queue BFS, we can use an unordered hash map and simply iterate from minHD to maxHD to collect the result. This runs in strict O(n) time.

When to apply: Optimal gold-standard solution for O(n) linear performance.

Algorithm

  1. Step 1: Initialize minHD = 0, maxHD = 0, unordered map bottomMap.
  2. Step 2: Queue stores pairs (node, hd). Push (root, 0).
  3. Step 3: While q is not empty: pop (node, hd); update minHD and maxHD; bottomMap[hd] = node.val.
  4. Step 4: Push children with hd - 1 and hd + 1.
  5. Step 5: Iterate for hd from minHD to maxHD: push bottomMap[hd] into answer list.

BFS Bottom View Trace for [1, 2, 3]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Dequeue root 1 with HD 0
Visual state
Values and pointers at this exact step
tree
Root
1 (HD 0)
L
2 (HD -1)
R
3 (HD +1)

Node order shown; add connections to display explicit tree edges.

hd: 0: 1
Check / comparison
map[0] = 1
Decision / next transition
Enqueue left child (HD -1) and right child (HD +1).
Why this step matters

Step 1: Dequeue root 1 with HD 0. map[0] = 1. Enqueue left child 2 (HD -1) and right child 3 (HD +1).

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> bottomView(TreeNode* root) {
10 if (!root) return {};
11 unordered_map<int, int> m;
12 queue<pair<TreeNode*, int>> q;
13 q.push({root, 0});
14 int minHd = 0, maxHd = 0;
15 while (!q.empty()) {
16 auto [node, hd] = q.front(); q.pop();
17 m[hd] = node->val;
18 minHd = min(minHd, hd);
19 maxHd = max(maxHd, hd);
20 if (node->left) q.push({node->left, hd - 1});
21 if (node->right) q.push({node->right, hd + 1});
22 }
23 vector<int> res;
24 for (int hd = minHd; hd <= maxHd; ++hd) {
25 res.push_back(m[hd]);
26 }
27 return res;
28 }
29};
30
31int main() {
32 // Sample driver execution
33 cout << "Execution completed successfully." << endl;
34 return 0;
35}
36

Time & Space Complexity

  • Time complexity: O(n) — All nodes processed in O(1) per node. Final iteration runs in O(w) <= O(n) without sorting.
  • Space complexity: O(n) — Hash map and queue take O(n) space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS with Depth TrackingO(n log n)O(n)Recursively visit nodes; update if current depth >= stored depth.Depth comparison logic and sorting.
2.BFS with Ordered MapO(n log w)O(n)Queue BFS unconditionally overwrites map; tree map keeps keys ordered.Tree map overhead.
3.BFS with Min/Max Bounds TrackingOptimalO(n)O(n)Queue BFS with O(1) hash map; loop from minHd to maxHd to extract answer.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single node: root = [1] -> [1].
  • Completely left-skewed: every node has HD = -level, so all nodes appear in bottom view.
  • Overlapping nodes at same level and HD: BFS visits left then right, so rightmost wins.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Contrast Bottom View with Top View: Top View only stores map[HD] if HD is NOT already present; Bottom View overwrites map[HD] unconditionally.
  2. Explain why DFS requires tracking depth (to overwrite only when depth >= current stored depth), making BFS simpler and cleaner.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does BFS allow unconditional overwrite map[hd] = node.val, whereas DFS requires comparing depths before overwriting?

Back to DSA Sheet