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.