Bottom View of Binary Tree in DSA Typescript - Deep Dive

Overview - Bottom View of Binary Tree

What is it?

The bottom view of a binary tree is the set of nodes visible when the tree is seen from the bottom. It shows the last node at each horizontal position when looking up from the ground. This view helps us understand the structure of the tree from a different angle than the usual top or side views.

Why it matters

Without the bottom view, we miss how nodes overlap vertically in a tree and which nodes hide others when seen from below. This concept is useful in graphical representations, network routing, and understanding hierarchical data from multiple perspectives. It helps solve problems where visibility or coverage from a certain viewpoint matters.

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 advanced tree algorithms.

Mental Model

Core Idea

The bottom view shows the last node visible at each horizontal position when looking at the tree from below.

Think of it like...

Imagine standing under a group of tall trees and looking up; the bottom view is like seeing the trunks that are directly above you, ignoring branches that are hidden behind others.

          (1)
         /   \
      (2)     (3)
       \       \
       (4)     (5)

Horizontal Distances:
Node 2: -1 | Node 1: 0 | Node 3: 1
Node 4: 0  | Node 5: 2

Bottom View: Nodes at HD -1, 0, 1, 2 => 2 -> 4 -> 3 -> 5

Build-Up - 6 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. Each node holds a value. The top node is called the root. Nodes connect downwards forming branches.

Result

You can visualize and represent data in a tree shape with nodes and edges.

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 (HD) to locate nodes relative to the root.

Assign HD=0 to the root. For left child, HD = parent's HD - 1. For right child, HD = parent's HD + 1. This helps map nodes to positions on a horizontal line.

Result

Each node has a horizontal distance value that helps identify its position relative to others.

Horizontal distance is the key to grouping nodes vertically for views like bottom or top view.

3

Intermediate

Traversing Tree with Horizontal Distances

🤔Before reading on: Do you think a simple preorder traversal can capture bottom view nodes correctly? Commit to your answer.

Concept: Use level order traversal (breadth-first) to visit nodes and track their horizontal distances.

Traverse the tree level by level using a queue. For each node, record its HD. This order ensures nodes closer to the bottom overwrite nodes above at the same HD.

Result

You get nodes in order from top to bottom and left to right, allowing correct bottom view calculation.

Level order traversal combined with HD tracking ensures the bottom-most nodes at each HD are captured.

4

Intermediate

Mapping Bottom View Nodes by Horizontal Distance

🤔Before reading on: Do you think the first node encountered at a horizontal distance is part of the bottom view? Commit to yes or no.

Concept: For each HD, keep updating the node value as you traverse. The last node at each HD is the bottom view node.

Use a map/dictionary with HD as key and node value as value. Update the map whenever a node at the same HD is found later in traversal.

Result

The map holds the bottom view nodes after traversal completes.

Knowing that the last node at each HD is visible from the bottom is crucial to correctly building the bottom view.

5

Advanced

Implementing Bottom View in TypeScript

🤔Before reading on: Predict the output of bottom view for a tree with nodes 1,2,3,4,5 arranged as in the visual. Commit to your answer.

Concept: Write a complete TypeScript function to compute bottom view using queue and map.

class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; constructor(val: number) { this.val = val; this.left = null; this.right = null; } } function bottomView(root: TreeNode | null): number[] { if (!root) return []; const hdMap = new Map(); const queue: Array<{node: TreeNode; hd: number}> = []; queue.push({node: root, hd: 0}); while (queue.length > 0) { const {node, hd} = queue.shift()!; hdMap.set(hd, node.val); // overwrite to keep bottom-most 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)!); } // Example tree construction and call const root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.right = new TreeNode(4); root.right.right = new TreeNode(5); console.log(bottomView(root));

Result

[2, 4, 3, 5]

Implementing bottom view with a queue and map shows how traversal order and HD tracking combine to solve the problem efficiently.

6

Expert

Handling Edge Cases and Optimizations

🤔Before reading on: Do you think nodes at the same horizontal distance but different depths always appear in bottom view? Commit to yes or no.

Concept: Explore cases with overlapping nodes, large trees, and memory optimizations.

Nodes at the same HD but deeper in the tree overwrite shallower ones in bottom view. For very large trees, use iterative traversal to avoid stack overflow. Use balanced trees or indexing to optimize lookups.

Result

Bottom view correctly reflects the lowest nodes per HD even in complex trees.

Understanding how depth and HD interact prevents errors in bottom view and guides efficient implementations.

Under the Hood

The algorithm uses a breadth-first traversal to visit nodes level by level. Each node is assigned a horizontal distance relative to the root. A map stores the latest node value seen at each horizontal distance. Because traversal is level order, nodes at lower levels overwrite earlier nodes at the same horizontal distance, ensuring the bottom-most node is recorded.

Why designed this way?

Breadth-first traversal ensures nodes are processed from top to bottom and left to right, which matches the natural way to find the bottom view. Using a map keyed by horizontal distance allows constant-time updates and retrieval. Alternatives like depth-first traversal would require more complex tracking and might miss the correct bottom nodes.

┌───────────────┐
│   Start root  │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Initialize    │
│ queue with    │
│ root, hd=0    │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ While queue   │
│ not empty:    │
│ Dequeue node  │
│ Update map[hd]│
│ Enqueue left  │
│ with hd-1     │
│ Enqueue right │
│ with hd+1     │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ After loop,   │
│ map has last  │
│ nodes per hd  │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Sort keys and │
│ output values │
└───────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does the first node encountered at a horizontal distance always appear in the bottom view? Commit yes or no.

Common Belief: The first node at a horizontal distance is the bottom view node.

Reality: The bottom view node is the last node encountered at that horizontal distance during level order traversal.

Why it matters: Choosing the first node leads to incorrect bottom views, missing nodes that are lower and visible from the bottom.

Quick: Can a simple preorder traversal correctly find the bottom view? Commit yes or no.

Common Belief: Any tree traversal can be used to find the bottom view.

Reality: Only level order traversal guarantees correct bottom view because it processes nodes by depth.

Why it matters: Using preorder or inorder can miss deeper nodes, resulting in wrong bottom view outputs.

Quick: Are nodes with the same horizontal distance but different depths always visible in the bottom view? Commit yes or no.

Common Belief: All nodes at the same horizontal distance appear in the bottom view.

Reality: Only the lowest (deepest) node at each horizontal distance is visible in the bottom view.

Why it matters: Misunderstanding this causes confusion about which nodes to include, leading to incorrect visualizations.

Expert Zone

1

The order of traversal is critical; level order ensures bottom-most nodes overwrite others, but subtle bugs occur if queue management is incorrect.

2

Horizontal distance alone is not enough; depth tracking ensures correct overwriting when nodes share HD but differ in level.

3

In trees with duplicate values, node identity matters; storing nodes instead of values can help in advanced applications.

When NOT to use

Bottom view is not suitable when you need the top view, left view, or right view of a tree, which require different traversal and tracking strategies. For non-binary trees or graphs, specialized algorithms are needed instead.

Production Patterns

Bottom view is used in graphical rendering engines to determine visible elements from below, in network routing to visualize layered connections, and in coding interviews to test understanding of tree traversals and mapping techniques.

Connections

Top View of Binary Tree

Opposite perspective of the same horizontal distance concept

Understanding bottom view clarifies how top view selects the first node at each horizontal distance, highlighting complementary visibility concepts.

Breadth-First Search (BFS)

Builds on BFS traversal technique

Knowing BFS deeply helps implement bottom view efficiently, as BFS processes nodes level by level, crucial for correct node overwriting.

Urban Planning - Skyline Problem

Similar problem of visibility from a viewpoint

Both bottom view and skyline problem involve determining visible elements from a perspective, showing how algorithms cross domains from trees to cityscapes.

Common Pitfalls

#1 Using preorder traversal to find bottom view nodes.

Wrong approach:

function bottomView(root) {
const hdMap = new Map();
function preorder(node, hd) {
if (!node) return;
hdMap.set(hd, node.val); // overwrites but order is wrong
preorder(node.left, hd - 1);
preorder(node.right, hd + 1);
}
preorder(root, 0);
return Array.from(hdMap.values());
}

Correct approach:

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

Root cause:

Misunderstanding that preorder does not process nodes level by level, so deeper nodes may not overwrite shallower ones correctly.

#2 Not sorting horizontal distances before output.

Wrong approach:

return Array.from(hdMap.values()); // unordered output

Correct approach:

const sortedKeys = Array.from(hdMap.keys()).sort((a,b) => a-b);
return sortedKeys.map(key => hdMap.get(key));

Root cause:

Ignoring that horizontal distances can be negative or unordered, causing output to be jumbled and not represent left-to-right bottom view.

Key Takeaways

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

Horizontal distance and level order traversal are essential tools to correctly identify bottom view nodes.

The last node encountered at each horizontal distance during level order traversal forms the bottom view.

Incorrect traversal methods or ignoring horizontal distance ordering lead to wrong bottom view results.

Bottom view algorithms have practical uses in visualization, routing, and understanding hierarchical data from new perspectives.