Bottom View of Binary Tree in DSA Javascript - Deep Dive

Overview - Bottom View of Binary Tree

What is it?

The bottom view of a binary tree shows the nodes visible when the tree is seen from below. Imagine looking up at the tree from the ground and noting which nodes you can see without any being hidden behind others. It is a way to represent the tree by showing the lowest nodes at each horizontal position. This helps understand the tree's structure from a different angle.

Why it matters

Without the bottom view, we miss how a tree looks from below, which can be important in problems like network routing, visualization, or understanding overlapping data. It helps in scenarios where the lowest visible elements matter, such as in graphical displays or layered data structures. Without this concept, we would only see the tree from top or sides, missing important perspectives.

Where it fits

Before learning bottom view, you should understand binary trees, tree traversal methods, and the concept of horizontal distance in trees. After this, you can explore related views like top view, left view, and right view of binary trees, and then move on to more complex tree algorithms like vertical order traversal.

Mental Model

Core Idea

The bottom view of a binary tree is the set of nodes visible when looking up from below, showing the lowest node at each horizontal position.

Think of it like...

Imagine standing under a tall tree and looking up. The bottom view is like seeing the leaves and branches that block your view of anything above them at each horizontal spot.

          (root)
           │
    ┌──────┴──────┐
   (L)           (R)

Horizontal distances:
   L: -1      root: 0      R: +1

Bottom view picks the lowest node at each horizontal distance.

Build-Up - 7 Steps

1

Foundation

Understanding Binary Trees Basics

Concept: Learn what a binary tree is and how nodes are connected.

A binary tree is a structure where each node has up to two children: left and right. The top node is called the root. Nodes below are connected by edges. Each node can have zero, one, or two children.

Result

You can visualize and identify nodes and their children in a binary tree.

Understanding the basic structure of binary trees is essential before exploring any specific views or traversals.

2

Foundation

Horizontal Distance Concept in Trees

Concept: Introduce horizontal distance to locate nodes relative to root.

Assign horizontal distance (HD) to each node: root is 0, left child is HD - 1, right child is HD + 1. This helps group nodes vertically.

Result

Each node has a horizontal distance value that helps in vertical grouping.

Knowing horizontal distance lets us organize nodes by vertical lines, which is key for bottom view.

3

Intermediate

Level Order Traversal with Horizontal Distance

🤔Before reading on: Do you think we can find bottom view by just looking at the last level of the tree? Commit to your answer.

Concept: Use level order traversal to visit nodes and track their horizontal distances.

We use a queue to visit nodes level by level. For each node, we note its horizontal distance. This helps us find which node is lowest at each horizontal distance.

Result

We get nodes in order of levels with their horizontal distances recorded.

Combining level order traversal with horizontal distance tracking allows us to identify the bottom-most nodes at each vertical line.

4

Intermediate

Mapping Horizontal Distance to Bottom Nodes

🤔Before reading on: Do you think the first node at a horizontal distance or the last node visited at that distance is part of the bottom view? Commit to your answer.

Concept: Update a map to keep the latest node seen at each horizontal distance during traversal.

As we traverse, we overwrite the node at each horizontal distance with the current node. Because level order visits top to bottom, the last node at each horizontal distance is the bottom view node.

Result

A map from horizontal distance to bottom view node is created.

Knowing that the last node visited at each horizontal distance is the bottom node helps us build the bottom view efficiently.

5

Intermediate

Extracting Bottom View from the Map

Concept: Sort the horizontal distances and print corresponding nodes.

After traversal, we sort the keys of the map (horizontal distances) from smallest to largest and print the nodes stored. This gives the bottom view from left to right.

Result

The bottom view nodes are printed in order from leftmost to rightmost.

Sorting horizontal distances ensures the bottom view is presented in a natural left-to-right order.

6

Advanced

JavaScript Implementation of Bottom View

🤔Before reading on: Do you think using a queue and a map is enough to implement bottom view in code? Commit to your answer.

Concept: Implement bottom view using queue for level order and map for horizontal distances in JavaScript.

```javascript class Node { constructor(data) { this.data = data; this.left = null; this.right = null; } } function bottomView(root) { if (!root) return []; const queue = []; const hdMap = new Map(); queue.push({ node: root, hd: 0 }); while (queue.length > 0) { const { node, hd } = queue.shift(); // Overwrite the map entry for hd hdMap.set(hd, node.data); if (node.left) queue.push({ node: node.left, hd: hd - 1 }); if (node.right) queue.push({ node: node.right, hd: hd + 1 }); } // Sort keys and prepare result const sortedKeys = Array.from(hdMap.keys()).sort((a, b) => a - b); return sortedKeys.map(key => hdMap.get(key)); } // Example usage: const root = new Node(20); root.left = new Node(8); root.right = new Node(22); root.left.left = new Node(5); root.left.right = new Node(3); root.right.left = new Node(4); root.right.right = new Node(25); root.left.right.left = new Node(10); root.left.right.right = new Node(14); console.log(bottomView(root)); ```

Result

[5, 10, 4, 14, 25]

Implementing bottom view with a queue and map in JavaScript shows how traversal and horizontal distance tracking combine to solve the problem.

7

Expert

Handling Edge Cases and Optimizations

🤔Before reading on: Do you think nodes with the same horizontal distance but different depths can cause issues in bottom view? Commit to your answer.

Concept: Understand how nodes at the same horizontal distance but different depths affect the bottom view and optimize accordingly.

If two nodes share the same horizontal distance, the one at the lower level (greater depth) should appear in the bottom view. Level order traversal naturally visits nodes top to bottom, so overwriting the map ensures the bottom-most node remains. For optimization, using a balanced tree or hash map with ordered keys can improve sorting performance.

Result

Bottom view correctly shows the lowest nodes even with overlapping horizontal distances.

Recognizing how traversal order affects which nodes appear in bottom view prevents bugs and improves correctness.

Under the Hood

The algorithm uses a breadth-first search (level order traversal) to visit nodes level by level. Each node is tagged with a horizontal distance relative to the root. A map stores the latest node data for each horizontal distance. Because level order visits nodes top to bottom, the last node stored for each horizontal distance is the bottom-most node visible from below.

Why designed this way?

This approach was chosen because level order traversal naturally processes nodes by depth, making it easy to overwrite nodes at the same horizontal distance with lower-level nodes. Alternatives like depth-first search would require extra tracking of depth and horizontal distance, complicating the logic.

┌───────────────┐
│   Start root  │
└──────┬────────┘
       │ hd=0
       ▼
┌───────────────┐
│ Enqueue root  │
└──────┬────────┘
       │
       ▼
┌─────────────────────────────┐
│ While queue not empty        │
│   Dequeue node and hd        │
│   Update map[hd] = node.data │
│   Enqueue left child hd-1    │
│   Enqueue right child hd+1   │
└─────────────┬───────────────┘
              │
              ▼
┌─────────────────────────────┐
│ After traversal, sort keys   │
│ and output map values        │
└─────────────────────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does the bottom view include all nodes at the lowest level? Commit yes or no.

Common Belief: The bottom view is just all nodes at the lowest level of the tree.

Reality: The bottom view includes the lowest node at each horizontal distance, which may not be all nodes at the lowest level.

Why it matters: Assuming all lowest level nodes are in the bottom view can cause incorrect results, missing nodes that are lower but horizontally aligned.

Quick: Can we find bottom view by only doing an inorder traversal? Commit yes or no.

Common Belief: Inorder traversal alone is enough to find the bottom view.

Reality: Inorder traversal does not track horizontal distances or levels properly, so it cannot reliably produce the bottom view.

Why it matters: Using inorder traversal alone leads to wrong bottom view because it misses the vertical and depth relationships.

Quick: If two nodes share the same horizontal distance, does the top one appear in bottom view? Commit yes or no.

Common Belief: The top node at a horizontal distance is part of the bottom view.

Reality: The bottom view shows the lowest node at that horizontal distance, so the top node is overwritten by lower nodes.

Why it matters: Misunderstanding this causes confusion and incorrect bottom view results.

Expert Zone

1

The order of traversal (level order) is critical; using preorder or postorder requires extra depth tracking to get correct bottom view.

2

Using a balanced tree or ordered map for horizontal distances can optimize sorting and retrieval of bottom view nodes.

3

In trees with duplicate horizontal distances and depths, tie-breaking rules may be needed for consistent bottom view.

When NOT to use

Bottom view is not suitable when you need the full vertical order traversal or top view. For those, use vertical order traversal algorithms or top view algorithms instead.

Production Patterns

Bottom view is used in graphical rendering engines to determine visible elements from below, in network routing to find lowest nodes in hierarchical structures, and in coding interviews to test understanding of tree traversals and horizontal distance concepts.

Connections

Top View of Binary Tree

Opposite perspective of bottom view, showing highest nodes at each horizontal distance.

Understanding bottom view helps grasp top view since both use horizontal distance but differ in which node (top or bottom) is chosen.

Vertical Order Traversal

Builds on horizontal distance grouping but lists all nodes per vertical line, not just bottom or top.

Knowing bottom view simplifies understanding vertical order traversal as a more detailed version of vertical grouping.

Shadow Casting in Computer Graphics

Similar concept of projecting 3D objects onto a 2D plane from a viewpoint.

Bottom view is like casting a shadow from below, helping understand visibility and occlusion in graphics.

Common Pitfalls

#1 Ignoring horizontal distance and only printing last level nodes.

Wrong approach:

function bottomView(root) {
// Just print last level nodes
if (!root) return [];
let queue = [root];
let lastLevel = [];
while (queue.length > 0) {
let size = queue.length;
lastLevel = [];
for (let i = 0; i < size; i++) {
let node = queue.shift();
lastLevel.push(node.data);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
return lastLevel;
}

Correct approach:

function bottomView(root) {
if (!root) return [];
const queue = [];
const hdMap = new Map();
queue.push({ node: root, hd: 0 });
while (queue.length > 0) {
const { node, hd } = queue.shift();
hdMap.set(hd, node.data);
if (node.left) queue.push({ node: node.left, hd: hd - 1 });
if (node.right) queue.push({ node: node.right, hd: hd + 1 });
}
const sortedKeys = Array.from(hdMap.keys()).sort((a, b) => a - b);
return sortedKeys.map(key => hdMap.get(key));
}

Root cause:

Misunderstanding that bottom view depends on horizontal distance, not just depth or level.

#2 Using depth-first traversal without tracking depth and horizontal distance properly.

Wrong approach:

function bottomView(root) {
const hdMap = new Map();
function dfs(node, hd) {
if (!node) return;
hdMap.set(hd, node.data); // overwrites without depth check
dfs(node.left, hd - 1);
dfs(node.right, hd + 1);
}
dfs(root, 0);
const sortedKeys = Array.from(hdMap.keys()).sort((a, b) => a - b);
return sortedKeys.map(key => hdMap.get(key));
}

Correct approach:

function bottomView(root) {
if (!root) return [];
const queue = [];
const hdMap = new Map();
queue.push({ node: root, hd: 0 });
while (queue.length > 0) {
const { node, hd } = queue.shift();
hdMap.set(hd, node.data);
if (node.left) queue.push({ node: node.left, hd: hd - 1 });
if (node.right) queue.push({ node: node.right, hd: hd + 1 });
}
const sortedKeys = Array.from(hdMap.keys()).sort((a, b) => a - b);
return sortedKeys.map(key => hdMap.get(key));
}

Root cause:

Not using level order traversal causes incorrect overwriting of nodes without considering depth.

Key Takeaways

Bottom view shows the lowest nodes visible at each horizontal distance when looking up from below a binary tree.

Horizontal distance is key to grouping nodes vertically and finding which nodes appear in the bottom view.

Level order traversal combined with horizontal distance tracking ensures correct identification of bottom view nodes.

The last node visited at each horizontal distance during level order traversal is the bottom view node.

Misunderstanding traversal methods or ignoring horizontal distance leads to incorrect bottom view results.