Bottom View of Binary Tree in DSA Javascript

Mental Model

We want to see the nodes visible if we look at the tree from the bottom. Each vertical line shows the lowest node at that horizontal distance.

Analogy: Imagine standing under a tree and looking up. You only see the lowest leaves or branches directly above you, not the ones hidden behind or higher up.

       20
      /  \
    8     22
   / \      \
  5   3      25
     / \      
    10  14    

Horizontal distances:
- 5 at -2
- 8 at -1
- 10 at 0 (lowest at this line)
- 14 at 1
- 22 at 2
- 25 at 3

Dry Run Walkthrough

Input: Binary tree: 20 / \ 8 22 / \ \ 5 3 25 / \ 10 14 Find bottom view

Goal: Find nodes visible from bottom, one per horizontal distance, showing the lowest node at each vertical line

Step 1: Start BFS from root (20) at horizontal distance 0

Queue: [(20, hd=0)]
Bottom view map: {}

Why: We begin from root to explore all nodes level by level with their horizontal distances

Step 2: Process node 20 at hd=0, update map hd=0 -> 20

Queue: [(8, hd=-1), (22, hd=1)]
Bottom view map: {0: 20}

Why: First node at hd=0 is 20, so map records it

Step 3: Process node 8 at hd=-1, update map hd=-1 -> 8

Queue: [(22, hd=1), (5, hd=-2), (3, hd=0)]
Bottom view map: {-1: 8, 0: 20}

Why: Node 8 is lowest so far at hd=-1; update map

Step 4: Process node 22 at hd=1, update map hd=1 -> 22

Queue: [(5, hd=-2), (3, hd=0), (25, hd=2)]
Bottom view map: {-1: 8, 0: 20, 1: 22}

Why: Node 22 is lowest so far at hd=1; update map

Step 5: Process node 5 at hd=-2, update map hd=-2 -> 5

Queue: [(3, hd=0), (25, hd=2)]
Bottom view map: {-2: 5, -1: 8, 0: 20, 1: 22}

Why: Node 5 is lowest so far at hd=-2; update map

Step 6: Process node 3 at hd=0, update map hd=0 -> 3 (overwrites 20)

Queue: [(25, hd=2), (10, hd=-1), (14, hd=1)]
Bottom view map: {-2: 5, -1: 8, 0: 3, 1: 22}

Why: Node 3 is lower than 20 at hd=0, so update map

Step 7: Process node 25 at hd=2, update map hd=2 -> 25

Queue: [(10, hd=-1), (14, hd=1)]
Bottom view map: {-2: 5, -1: 8, 0: 3, 1: 22, 2: 25}

Why: Node 25 is lowest so far at hd=2; update map

Step 8: Process node 10 at hd=-1, update map hd=-1 -> 10 (overwrites 8)

Queue: [(14, hd=1)]
Bottom view map: {-2: 5, -1: 10, 0: 3, 1: 22, 2: 25}

Why: Node 10 is lower than 8 at hd=-1, update map

Step 9: Process node 14 at hd=1, update map hd=1 -> 14 (overwrites 22)

Queue: []
Bottom view map: {-2: 5, -1: 10, 0: 3, 1: 14, 2: 25}

Why: Node 14 is lower than 22 at hd=1, update map

Result:

Bottom view nodes by horizontal distance:
-2: 5 -> -1: 10 -> 0: 3 -> 1: 14 -> 2: 25
Answer: 5 10 3 14 25

Annotated Code

DSA 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(); // horizontal distance to node data
  queue.push({ node: root, hd: 0 });

  while (queue.length > 0) {
    const { node, hd } = queue.shift();
    // overwrite map at hd with current node data
    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 collect values
  const sortedKeys = Array.from(hdMap.keys()).sort((a, b) => a - b);
  return sortedKeys.map(k => hdMap.get(k));
}

// Driver code
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.right = new Node(25);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);

const result = bottomView(root);
console.log(result.join(' '));

queue.push({ node: root, hd: 0 });

start BFS from root with horizontal distance 0

const { node, hd } = queue.shift();

dequeue next node and its horizontal distance

hdMap.set(hd, node.data);

update map to keep lowest node at this horizontal distance

if (node.left) queue.push({ node: node.left, hd: hd - 1 });

enqueue left child with hd - 1

if (node.right) queue.push({ node: node.right, hd: hd + 1 });

enqueue right child with hd + 1

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

sort horizontal distances to output bottom view left to right

return sortedKeys.map(k => hdMap.get(k));

collect bottom view nodes in order

Output

5 10 3 14 25

Complexity Analysis

Time: O(n) because we visit each node once in BFS

Space: O(n) for queue and map storing nodes and horizontal distances

vs Alternative: Naive approach might try vertical traversal multiple times causing more than O(n) time; BFS with map is efficient

Edge Cases

Empty tree

Returns empty array as no nodes exist

DSA Javascript

if (!root) return [];

Single node tree

Returns array with single node data

DSA Javascript

queue.push({ node: root, hd: 0 });

All nodes on one side (left skewed)

Bottom view shows all nodes with decreasing horizontal distance

DSA Javascript

if (node.left) queue.push({ node: node.left, hd: hd - 1 });

When to Use This Pattern

When asked to find nodes visible from bottom or side in a tree, use BFS with horizontal distance mapping to track lowest nodes per vertical line.

Common Mistakes

Mistake: Not updating the map to overwrite nodes at the same horizontal distance, so top nodes remain instead of bottom
Fix: Always overwrite the map entry for horizontal distance during BFS to keep the lowest node

Mistake: Using DFS which may not process nodes level by level, causing incorrect bottom view
Fix: Use BFS to process nodes level-wise ensuring bottom nodes overwrite top nodes

Summary

Finds the nodes visible when looking at a binary tree from the bottom by tracking horizontal distances.

Use when you need to see the lowest nodes at each vertical line of a binary tree.

The key insight is to do a level order traversal while recording and updating nodes by their horizontal distance.

Practice

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

easy

A. Nodes visible when the tree is viewed from the right 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 left side

Solution

1. Step 1: Understand the bottom view concept

   The bottom view shows nodes 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 from above, left and right views show nodes from sides, so bottom view is unique for bottom perspective.

3. Final Answer:

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

4. Quick Check:

   Bottom view = nodes visible 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 side views

2. Which of the following JavaScript code snippets correctly initializes a Map to store horizontal distances and nodes for bottom view?

easy

A. const map = new Map();

B. const map = {};

C. const map = new Array();

D. const map = new Set();

Solution

1. Step 1: Identify suitable data structure for key-value pairs

   Map is ideal for storing horizontal distance as key and node data as value with easy insertion and retrieval.

2. Step 2: Check other options

   Object ({}) can be used but Map is preferred for ordered keys and better methods; Array and Set are not suitable for key-value pairs.

3. Final Answer:

   const map = new Map(); -> Option A

4. Quick Check:

   Use Map for horizontal distance mapping [OK]

Hint: Use Map() for key-value storage in bottom view [OK]

Common Mistakes:

• Using Array instead of Map for key-value pairs
• Using Set which stores only unique values, not key-value
• Using plain object without considering key types

3. Consider the following binary tree and code snippet to print its bottom view:

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

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.right = new Node(25);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);

// Bottom view logic omitted for brevity
// Assume correct implementation

// Output bottom view nodes in order of horizontal distance
// What is the bottom view output?

medium

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

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

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

D. [8, 10, 3, 14, 25]

Solution

1. Step 1: Assign horizontal distances and track bottom nodes

   Assign horizontal distances: 20(0), 8(-1), 22(1), 5(-2), 3(0), 25(2), 10(-1), 14(1). Bottom view keeps last node at each horizontal distance.

2. Step 2: Determine bottom nodes at each horizontal distance

   At -2: 5; at -1: 10 (overwrites 8); at 0: 3 (overwrites 20); at 1: 14 (overwrites 22); at 2: 25.

3. Final Answer:

   [5, 10, 3, 14, 25] -> Option B

4. Quick Check:

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

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

Common Mistakes:

• Using first node instead of last at horizontal distance
• Mixing horizontal distances incorrectly
• Ignoring overwriting nodes at same horizontal distance

4. The following code attempts to print the bottom view of a binary tree but produces incorrect output. What is the main issue?

function bottomView(root) {
  const map = new Map();
  const queue = [];
  queue.push({ node: root, hd: 0 });

  while (queue.length > 0) {
    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 stores only the first node at each horizontal distance, not the bottom-most

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

C. It does not handle null root input

D. It uses Map instead of Object for storage

Solution

1. Step 1: Analyze map update condition

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

2. Step 2: Understand bottom view requirement

   Bottom view requires last node at each horizontal distance (lowest level), so map should update value every time a node at same hd is found.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Not updating map on repeated horizontal distances
• Confusing top view logic with bottom view
• Ignoring queue inefficiency but that doesn't affect correctness

5. Given a binary tree where multiple nodes share the same horizontal distance and level, 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 leftmost node at that horizontal distance and level

C. Display the rightmost node at that horizontal distance and level

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

Solution

1. Step 1: Understand node conflicts at same horizontal distance and level

   When nodes share horizontal distance and level, bottom view shows the one visible from bottom, which is the one encountered last in level order traversal.

2. Step 2: Reason about traversal order

   Level order traversal processes nodes left to right at each level, so last encountered node at hd and level overwrites previous.

3. Final Answer:

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

4. Quick Check:

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

Hint: Use last node in level order traversal for bottom view [OK]

Common Mistakes:

• Choosing leftmost or rightmost arbitrarily
• Choosing node by value instead of position
• Ignoring traversal order impact