Bottom View of Binary Tree in DSA Typescript

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 position.

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:
- 20 at 0
- 8 at -1
- 22 at 1
- 5 at -2
- 3 at 0
- 25 at 2
- 10 at -1
- 14 at 1

Dry Run Walkthrough

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

Goal: Find nodes visible from bottom: one node per horizontal distance, the lowest one in the tree

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: Pop (20,0), update bottom view at hd=0 with 20

Queue: []
Bottom view map: {0: 20}

Why: First node at hd=0 is 20, so bottom view at 0 is 20

Step 3: Add left child (8, hd=-1) and right child (22, hd=1) to queue

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

Why: Children are added with updated horizontal distances

Step 4: Pop (8,-1), update bottom view at hd=-1 with 8

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

Why: First node at hd=-1 is 8

Step 5: Add left child (5,-2) and right child (3,0) of 8 to queue

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

Why: Add children with their horizontal distances

Step 6: Pop (22,1), update bottom view at hd=1 with 22

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

Why: First node at hd=1 is 22

Step 7: Add right child (25,2) of 22 to queue

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

Why: Add child with hd=2

Step 8: Pop (5,-2), update bottom view at hd=-2 with 5

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

Why: First node at hd=-2 is 5

Step 9: Pop (3,0), update bottom view at hd=0 with 3 (overwrite 20)

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

Why: 3 is lower than 20 at hd=0, so update bottom view

Step 10: Add left child (10,-1) and right child (14,1) of 3 to queue

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

Why: Add children with their horizontal distances

Step 11: Pop (25,2), update bottom view at hd=2 with 25

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

Why: First node at hd=2 is 25

Step 12: Pop (10,-1), update bottom view at hd=-1 with 10 (overwrite 8)

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

Why: 10 is lower than 8 at hd=-1, update bottom view

Step 13: Pop (14,1), update bottom view at hd=1 with 14 (overwrite 22)

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

Why: 14 is lower than 22 at hd=1, update bottom view

Result:

-2: 5 -> -1: 10 -> 0: 3 -> 1: 14 -> 2: 25
Bottom view nodes: 5 10 3 14 25

Annotated Code

DSA Typescript

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 [];

  // Map to store the bottom view nodes: hd -> node.val
  const hdNodeMap = new Map<number, number>();

  // Queue for BFS: stores pairs of node and its horizontal distance
  const queue: Array<{node: TreeNode; hd: number}> = [];
  queue.push({node: root, hd: 0});

  while (queue.length > 0) {
    const {node, hd} = queue.shift()!;

    // Update bottom view for this horizontal distance
    hdNodeMap.set(hd, node.val);

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

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

  // Extract bottom view nodes sorted by horizontal distance
  const sortedKeys = Array.from(hdNodeMap.keys()).sort((a, b) => a - b);
  return sortedKeys.map(key => hdNodeMap.get(key)!);
}

// Driver code to build tree and print bottom view
const root = new TreeNode(20);
root.left = new TreeNode(8);
root.right = new TreeNode(22);
root.left.left = new TreeNode(5);
root.left.right = new TreeNode(3);
root.right.right = new TreeNode(25);
root.left.right.left = new TreeNode(10);
root.left.right.right = new TreeNode(14);

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

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

Initialize BFS queue with root at horizontal distance 0

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

Dequeue next node and its horizontal distance for processing

hdNodeMap.set(hd, node.val);

Update bottom view map with current node at this horizontal distance

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

Add left child with horizontal distance one less

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

Add right child with horizontal distance one more

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

Sort horizontal distances to output bottom view left to right

return sortedKeys.map(key => hdNodeMap.get(key)!);

Return bottom view nodes in order of horizontal distance

Output

5 10 3 14 25

Complexity Analysis

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

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

vs Alternative: Compared to recursive vertical order traversal, BFS with map is simpler and efficient for bottom view

Edge Cases

Empty tree (root is null)

Returns empty array as there are no nodes

DSA Typescript

if (!root) return [];

Tree with single node

Returns array with only that node's value

DSA Typescript

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

Tree with all nodes on one side (left or right)

Bottom view is all nodes in a line with increasing or decreasing horizontal distances

DSA Typescript

hdNodeMap.set(hd, node.val);

When to Use This Pattern

When asked to find nodes visible from bottom or side in a tree, use BFS with horizontal distances to track and update visible nodes.

Common Mistakes

Mistake: Not updating the bottom view map when a lower node at the same horizontal distance is found
Fix: Always overwrite the map entry for a 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 by level ensuring bottom nodes overwrite top ones

Summary

Finds the nodes visible when looking at a binary tree from the bottom.

Use when you need to see the lowest nodes at each horizontal position in a tree.

The key is to track horizontal distances and overwrite nodes at each distance during a level order traversal.