Bottom View of Binary Tree

62.4k
0

Given the root of a binary tree, return its bottom view from left to right.

The bottom view contains the nodes visible when the tree is observed from below. For every vertical position, the deepest node on that vertical line is visible.

To identify vertical positions, a horizontal distance (hd) is assigned to every node. It represents the horizontal position of a node relative to the root:

  • The root has hd = 0.

  • The left child has hd = parentHD - 1.

  • The right child has hd = parentHD + 1.

If multiple nodes lie at the same horizontal distance and depth, the node encountered later in level-order traversal is considered visible.

The visible node values must be returned from the smallest horizontal distance to the largest.

Example 1

Input: root = [1, 2, 3, 4, 5, 6, 7]

Output: [4, 2, 6, 3, 7]

Explanation: The deepest visible nodes from the leftmost to the rightmost vertical line are 4, 2, 6, 3, 7. Nodes 1 and 5 are hidden by deeper nodes lying on the same vertical positions.

Example 2

Input: root = [20, 8, 22, 5, 3, null, 25, null, null, 10, 14]

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

Explanation: For each horizontal distance, the deepest node is selected. Therefore, the bottom view from left to right is 5, 10, 3, 14, 25.

Brute Force Approach

Nodes having the same horizontal distance (hd) belong to the same vertical line. Here, hd is used to identify which nodes compete for the same position in the bottom view.

For each vertical line, the node having the greatest depth must be selected because it is the closest node to an observer looking from below.

Therefore, every node can be recorded along with its horizontal distance, level, and traversal order. The level determines which node is deeper, while traversal order is used to resolve the case where two nodes occur at the same horizontal distance and depth.

After all nodes have been collected, the entries are sorted so that nodes belonging to the same vertical line are grouped together. The last suitable entry for each horizontal distance becomes part of the bottom view.

The approach is straightforward, but storing and sorting all N nodes introduces an additional O(N log N) cost.

Algorithm

  • Every node is traversed level by level, and its horizontalDistance, level, and traversal order are recorded so that both its vertical position and depth can be determined.

  • The root is assigned horizontal distance 0 and level 0. A left child is assigned hd - 1, while a right child is assigned hd + 1.

  • All stored entries are sorted by horizontal distance, then by level, and finally by traversal order so that deeper and later nodes can be identified correctly.

  • For each horizontal distance, the last valid entry in the sorted group is selected because it represents the deepest node, while later traversal order resolves equal-depth ties.

  • The selected values are returned from the smallest horizontal distance to the largest.

Dry Run

Bottom View of Binary Tree Brute Force Dry Run.png

Bottom View of Binary Tree Brute Force Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
private:
struct NodeInfo {
int hd;
int level;
int order;
int value;
};
public:
// Stores every node with its horizontal distance,
// depth, and level-order traversal position.
vector<int> bottomView(TreeNode* root) {
// An empty tree has no bottom view.
if (root == nullptr) {
return {};
}
vector<NodeInfo> nodes;
queue<tuple<TreeNode*, int, int>> nodesQueue;
nodesQueue.push({root, 0, 0});
int order = 0;
while (!nodesQueue.empty()) {
auto [node, hd, level] =
nodesQueue.front();
nodesQueue.pop();
nodes.push_back({
hd,
level,
order++,
node->val
});
if (node->left != nullptr) {
nodesQueue.push({
node->left,
hd - 1,
level + 1
});
}
if (node->right != nullptr) {
nodesQueue.push({
node->right,
hd + 1,
level + 1
});
}
}
// Sorting by hd groups one vertical line together.
// Greater level and later BFS order then appear last.
sort(
nodes.begin(),
nodes.end(),
[](const NodeInfo& a, const NodeInfo& b) {
if (a.hd != b.hd) {
return a.hd < b.hd;
}
if (a.level != b.level) {
return a.level < b.level;
}
return a.order < b.order;
}
);
vector<int> answer;
int i = 0;
while (i < nodes.size()) {
int j = i;
while (
j + 1 < nodes.size() &&
nodes[j + 1].hd == nodes[i].hd
) {
j++;
}
// The last node in this hd group is deepest.
// For equal depth, later level-order traversal wins.
answer.push_back(nodes[j].value);
i = j + 1;
}
return answer;
}
};
int main() {
TreeNode* root = new TreeNode(20);
root->left = new TreeNode(8);
root->right = new TreeNode(22);
root->left->left = new TreeNode(5);
root->left->right = new TreeNode(3);
root->right->right = new TreeNode(25);

Complexity Analysis

Time Complexity: O(N log N), where N is the number of nodes in the binary tree. All N nodes are stored and then sorted.

Space Complexity: O(N), where N is the number of nodes in the binary tree. Information for every node may be stored before the final answer is constructed.

Better Approach

Sorting information for every node is unnecessary because only the best candidate for each horizontal distance needs to be retained.

During DFS, two values are tracked:

  • hd represents the horizontal distance of the current node from the root and identifies its vertical line.

  • level represents the depth of the current node.

For every horizontal distance, an ordered map stores the current bottom-view candidate together with its storedLevel. The storedLevel represents the greatest depth seen so far at that horizontal distance.

If another node reaches the same horizontal distance at a deeper level, it must replace the stored node because it lies lower in the tree. If it is reached at the same level, it is also allowed to replace the previous node so that the later traversal candidate receives priority.

Because an ordered map keeps horizontal distances sorted, the answer can be collected directly from left to right after DFS finishes.

Algorithm

  • DFS is started from the root with horizontal distance 0 and level 0, while an ordered map is maintained to store the deepest storedLevel and corresponding node value for every horizontal distance.

  • When a horizontal distance is encountered for the first time, the current node and its level are stored because no better candidate is known yet.

  • If the same horizontal distance has already been recorded, its value is replaced whenever currentLevel >= storedLevel, allowing deeper nodes and later equal-depth nodes to become the visible candidate.

  • The left subtree is explored with hd - 1 and the right subtree with hd + 1, so the correct vertical positions are preserved throughout the traversal.

  • After DFS is completed, the ordered map is read from the smallest horizontal distance to the largest to construct the bottom view.

Dry Run

Bottom View of Binary Tree Better Appraoch Dry Run.png

Bottom View of Binary Tree Better Appraoch Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
private:
// Stores {deepest level, node value}
// for every horizontal distance.
void dfs(
TreeNode* node,
int hd,
int level,
map<int, pair<int, int>>& bottom
) {
// Null children do not contribute
// any candidate to the bottom view.
if (node == nullptr) {
return;
}
// A deeper node must replace the old candidate.
// At equal depth, the later DFS candidate is used.
if (
bottom.find(hd) == bottom.end() ||
level >= bottom[hd].first
) {
bottom[hd] = {
level,
node->val
};
}
// Left-first DFS preserves left-to-right order
// among nodes that lie at the same depth.
dfs(
node->left,
hd - 1,
level + 1,
bottom
);
dfs(
node->right,
hd + 1,
level + 1,
bottom
);
}
public:
vector<int> bottomView(TreeNode* root) {
// An empty tree has no visible nodes.
if (root == nullptr) {
return {};
}
map<int, pair<int, int>> bottom;
dfs(
root,
0,
0,
bottom
);
vector<int> answer;
// map keeps horizontal distances ordered,
// so values are collected left to right.
for (auto& entry : bottom) {
answer.push_back(
entry.second.second
);
}
return answer;
}
};
int main() {
TreeNode* root = new TreeNode(20);
root->left = new TreeNode(8);
root->right = new TreeNode(22);
root->left->left = new TreeNode(5);
root->left->right = new TreeNode(3);
root->right->right = new TreeNode(25);
root->left->right->left = new TreeNode(10);
root->left->right->right = new TreeNode(14);
Solution solution;
vector<int> result =
solution.bottomView(root);
for (int value : result) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), where N is the number of nodes in the binary tree. Every node is visited once, and ordered-map operations can require O(log N) time.

Space Complexity: O(N), where N is the number of nodes in the binary tree. The ordered map may store entries for multiple horizontal distances, while the recursion stack can also require up to O(N) space in the worst case.

Optimal Approach

BFS is particularly suitable for the Bottom View because nodes are processed level by level, from shallower levels toward deeper levels.

Here, hd identifies the vertical line of the current node. Unlike Top View, where the first node at each horizontal distance is retained, the Bottom View requires the stored value to be overwritten whenever another node is encountered at the same hd.

Since BFS visits deeper levels later, the most recently stored value naturally becomes the deepest visible node. If two nodes occur at the same depth and horizontal distance, the node encountered later in BFS also replaces the earlier one, satisfying the required tie rule.

Two additional variables are maintained:

  • minHD stores the smallest horizontal distance reached and identifies the leftmost vertical line.

  • maxHD stores the largest horizontal distance reached and identifies the rightmost vertical line.

These boundaries allow the final answer to be collected directly from minHD to maxHD without sorting the horizontal distances afterward.

Algorithm

  • If the root is null, an empty result is returned because no node is visible.

  • The pair (root, 0) is inserted into a queue, while a map is maintained from horizontal distance to the most recently encountered node value. The variables minHD and maxHD are initialized to 0 to track the horizontal range covered by the tree.

  • During BFS, the value stored for the current hd is overwritten by the current node, because nodes processed later are either deeper or receive priority when depth is equal.

  • The left child is inserted with hd - 1 and the right child with hd + 1, while minHD and maxHD are updated whenever a new horizontal extreme is reached.

  • After BFS is completed, the stored values are collected from minHD through maxHD so that the bottom view is returned from left to right.

Dry Run

Bottom View of Binary Tree Optimal Appraoch Dry Run.png

Bottom View of Binary Tree Optimal Appraoch Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
public:
vector<int> bottomView(TreeNode* root) {
// An empty tree has no bottom view.
if (root == nullptr) {
return {};
}
unordered_map<int, int> bottom;
queue<pair<TreeNode*, int>> nodesQueue;
nodesQueue.push({root, 0});
int minHD = 0;
int maxHD = 0;
while (!nodesQueue.empty()) {
TreeNode* node =
nodesQueue.front().first;
int hd =
nodesQueue.front().second;
nodesQueue.pop();
// Every later node at the same hd overwrites
// the earlier one, giving priority to deeper
// nodes and later equal-depth BFS nodes.
bottom[hd] = node->val;
if (node->left != nullptr) {
int leftHD = hd - 1;
nodesQueue.push({
node->left,
leftHD
});
// minHD tracks the leftmost vertical line
// reached so final sorting is unnecessary.
minHD = min(minHD, leftHD);
}
if (node->right != nullptr) {
int rightHD = hd + 1;
nodesQueue.push({
node->right,
rightHD
});
// maxHD tracks the rightmost vertical line
// reached so values can be read left to right.
maxHD = max(maxHD, rightHD);
}
}
vector<int> answer;
// Every hd between the two extremes is read
// in order to produce the left-to-right view.
for (int hd = minHD; hd <= maxHD; hd++) {
answer.push_back(bottom[hd]);
}
return answer;
}
};
int main() {
TreeNode* root = new TreeNode(20);
root->left = new TreeNode(8);
root->right = new TreeNode(22);
root->left->left = new TreeNode(5);
root->left->right = new TreeNode(3);
root->right->right = new TreeNode(25);
root->left->right->left = new TreeNode(10);
root->left->right->right = new TreeNode(14);
Solution solution;
vector<int> result =
solution.bottomView(root);
for (int value : result) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N) on average, where N is the number of nodes in the binary tree. Every node is processed once, and hash-map operations take O(1) average time.

Space Complexity: O(N), where N is the number of nodes in the binary tree. The BFS queue and horizontal-distance map may together store information for up to all nodes.

FAQs

Q1. Why is horizontal distance required for the Bottom View?

Horizontal distance identifies which nodes lie on the same vertical line. Since only one node from each vertical line can appear in the Bottom View, it allows the competing nodes to be grouped correctly.

Q2. How is Bottom View different from Top View?

Top View keeps the shallowest node at each horizontal distance, whereas Bottom View keeps the deepest node. Therefore, Top View usually preserves the first valid candidate, while Bottom View allows later candidates to replace earlier ones.

Q3. How is Bottom View different from Vertical Order Traversal?

Bottom View keeps only one deepest visible node from each horizontal distance. Vertical Order Traversal can include all nodes lying on the same vertical line.

Q4. How is Bottom View different from Top View?

Top View keeps the first or shallowest node at each horizontal distance. Bottom View keeps the deepest node, so previously stored values may be replaced.

Q5. Why does the DFS approach need to track level?

DFS does not process nodes in increasing depth order. A deeper node may be visited before or after another candidate, so the level must be stored explicitly to determine which node is actually visible from below.

Binary Tree

Read Similar Blogs

Binary Tree

Parent and Distance - Introduction

Parent and Distance in a Binary Tree A binary tree normally stores connections from a node to its children: Left child Right child These connections make downward traversal straightforward. However...

117.9k
Binary Tree

Check If a Binary Tree Is a Subtree of Another Tree

Given the roots of two binary trees, root and subRoot , determine whether subRoot appears as a subtree of root . A subtree must match an entire tree section starting from some node in root , includ...

67.9k
Binary Tree

Count Nodes in a Complete Binary Tree

Input: root = [1, 2, 3, 4, 5, 6] Output: 6 Explanation: The binary tree contains a total of 6 nodes. Input: root = [1] Output: 1 Explanation: The tree contains only its root node, so the total numb...

54.2k
Comments0