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.

Practice

1. What does the bottom view of a binary tree represent?

easy

A. Nodes visible when the tree is viewed from the left side

B. Nodes visible when the tree is viewed from the top

C. Nodes visible when the tree is viewed from the bottom

D. Nodes visible when the tree is viewed from the right side

Solution

1. Step 1: Understand the bottom view concept

   The bottom view of a binary tree includes nodes that are visible when looking at the tree from below, meaning the lowest nodes at each horizontal distance.

2. Step 2: Compare with other views

   Top view shows nodes visible from above, left view from left side, right view from right side. Bottom view is distinct as it shows the lowest nodes at each horizontal position.

3. Final Answer:

   Nodes visible when the tree is viewed from the bottom -> Option C

4. Quick Check:

   Bottom view = visible nodes from below [OK]

Hint: Bottom view shows lowest nodes at each horizontal distance [OK]

Common Mistakes:

• Confusing bottom view with top view
• Thinking bottom view shows all leaf nodes
• Mixing bottom view with left or right side views

2. Which TypeScript data structure is best suited to store nodes by their horizontal distance when computing the bottom view?

easy

A. Array

B. Map (key-value pairs)

C. Set

D. Stack

Solution

1. Step 1: Identify the need to map horizontal distances

   We need to associate each horizontal distance with the node visible at that distance in the bottom view.

2. Step 2: Choose a data structure for key-value mapping

   A Map allows storing keys (horizontal distances) with corresponding node values, enabling easy updates and retrieval.

3. Final Answer:

   Map (key-value pairs) -> Option B

4. Quick Check:

   Use Map for horizontal distance to node mapping [OK]

Hint: Use Map to link horizontal distance with nodes [OK]

Common Mistakes:

• Using Array which is index-based, not key-based
• Using Set which stores unique values but no keys
• Using Stack which is LIFO, not suitable for mapping

3. What is the output bottom view of the binary tree represented by the following code?

class Node {
  constructor(public data: number, public left: Node | null = null, public right: Node | null = null) {}
}

const root = new Node(20,
  new Node(8,
    new Node(5),
    new Node(3, null, new Node(10))
  ),
  new Node(22, null, new Node(25))
);

medium

A. [5, 8, 3, 10, 25]

B. [5, 10, 3, 22, 25]

C. [8, 3, 10, 22, 25]

D. [5, 3, 10, 22, 25]

Solution

1. Step 1: Assign horizontal distances and track nodes

   Horizontal distances: 20(0), 8(-1), 22(1), 5(-2), 3(0), 10(1), 25(2). Level order traversal order: 20(0), 8(-1), 22(1), 5(-2), 3(0), 25(2), 10(1). For bottom view, the last node encountered at each hd.

2. Step 2: Determine bottom view nodes by horizontal distance

   hd -2:5; -1:8; 0:3 (overwrites 20); 1:10 (overwrites 22); 2:25. Sorted left-to-right: [5, 8, 3, 10, 25].

3. Final Answer:

   [5, 8, 3, 10, 25] -> Option A

4. Quick Check:

   Bottom view nodes = [5, 8, 3, 10, 25] [OK]

Hint: Track last node at each horizontal distance [OK]

Common Mistakes:

• Choosing first node at horizontal distance instead of last
• Mixing horizontal distances incorrectly
• Ignoring right child nodes at same horizontal distance

4. Identify the bug in this TypeScript code snippet for bottom view of a binary tree:

function bottomView(root: Node | null): number[] {
  if (!root) return [];
  const map = new Map();
  const queue: Array<{node: Node; hd: number}> = [{node: root, hd: 0}];
  while (queue.length) {
    const {node, hd} = queue.shift()!;
    if (!map.has(hd)) {
      map.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});
  }
  return Array.from(map.values());
}

medium

A. It only stores the first node at each horizontal distance, not the bottom-most

B. It uses shift() which is inefficient for queue

C. It does not check if root is null

D. It returns keys instead of values from the map

Solution

1. Step 1: Analyze map update condition

   The code sets map value only if horizontal distance is not present, so it keeps the first node at that distance.

2. Step 2: Understand bottom view requirement

   Bottom view requires the last (bottom-most) node at each horizontal distance, so map should update value every time a node at that hd is found.

3. Final Answer:

   It only stores the first node at each horizontal distance, not the bottom-most -> Option A

4. Quick Check:

   Bottom view needs last node per hd, code stores first [OK]

Hint: Update map value for every node at horizontal distance [OK]

Common Mistakes:

• Not updating map for later nodes at same horizontal distance
• Confusing top view logic with bottom view
• Ignoring null root check (though present here)

5. Given a binary tree where multiple nodes share the same horizontal distance and depth, how should the bottom view algorithm decide which node to display?

hard

A. Display the node with the smallest value at that horizontal distance

B. Display the node with the largest depth but smallest horizontal distance

C. Display the node that appears first in level order traversal at that horizontal distance

D. Display the node that appears last in level order traversal at that horizontal distance

Solution

1. Step 1: Understand node selection criteria for bottom view

   Bottom view shows the lowest node at each horizontal distance. When multiple nodes share horizontal distance and depth, the one encountered last in level order traversal is visible.

2. Step 2: Clarify why last in level order matters

   Level order visits nodes top to bottom, left to right. The last node at a horizontal distance overwrites previous ones, ensuring bottom-most visibility.

3. Final Answer:

   Display the node that appears last in level order traversal at that horizontal distance -> Option D

4. Quick Check:

   Bottom view = last node per hd in level order [OK]

Hint: Choose last node at horizontal distance in level order [OK]

Common Mistakes:

• Choosing node by value instead of position
• Selecting first node instead of last at horizontal distance
• Confusing horizontal distance with depth