Bottom View of Binary Tree in DSA Go

Mental Model

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

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

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

Vertical lines: -2  -1   0   1   2
Nodes:          5  10  3  14  25

Dry Run Walkthrough

Input: Binary tree: root=20, left=8, right=22, 8's left=5, 8's right=3, 3's left=10, 3's right=14, 22's right=25

Goal: Find the bottom view nodes of the tree, showing the lowest node at each vertical line

Step 1: Start at root 20 with horizontal distance (hd) 0

hd=0: 20
Tree: 20
     /  \
    8    22

Why: Root is the starting point with hd=0

Step 2: Visit left child 8 with hd -1, update bottom view at hd -1 to 8

hd=-1: 8
hd=0: 20
Tree: 20
     /  \
    8    22

Why: Left child is one step left, so hd decreases by 1

Step 3: Visit right child 22 with hd 1, update bottom view at hd 1 to 22

hd=-1: 8
hd=0: 20
hd=1: 22
Tree: 20
     /  \
    8    22

Why: Right child is one step right, so hd increases by 1

Step 4: Visit 8's left child 5 with hd -2, update bottom view at hd -2 to 5

hd=-2: 5
hd=-1: 8
hd=0: 20
hd=1: 22
Tree: 20
     /  \
    8    22
   /

Why: Left child of 8 is one step left from hd -1

Step 5: Visit 8's right child 3 with hd 0, update bottom view at hd 0 to 3 (overwrites 20)

hd=-2: 5
hd=-1: 8
hd=0: 3
hd=1: 22
Tree: 20
     /  \
    8    22
   / \

Why: 3 is lower than 20 at hd 0, so it overwrites

Step 6: Visit 3's left child 10 with hd -1, update bottom view at hd -1 to 10 (overwrites 8)

hd=-2: 5
hd=-1: 10
hd=0: 3
hd=1: 22
Tree: 20
     /  \
    8    22
   / \  
  5   3
     /

Why: 10 is lower than 8 at hd -1, so it overwrites

Step 7: Visit 3's right child 14 with hd 1, update bottom view at hd 1 to 14 (overwrites 22)

hd=-2: 5
hd=-1: 10
hd=0: 3
hd=1: 14
Tree: 20
     /  \
    8    22
   / \  
  5   3
     / \

Why: 14 is lower than 22 at hd 1, so it overwrites

Step 8: Visit 22's right child 25 with hd 2, update bottom view at hd 2 to 25

hd=-2: 5
hd=-1: 10
hd=0: 3
hd=1: 14
hd=2: 25
Tree: 20
     /  \
    8    22
   / \     \
  5   3     25

Why: Right child of 22 is one step right from hd 1

Result:

Bottom view nodes by hd ascending: 5 -> 10 -> 3 -> 14 -> 25

Annotated Code

DSA Go

package main

import (
	"container/list"
	"fmt"
)

type Node struct {
	Val   int
	Left  *Node
	Right *Node
}

func bottomView(root *Node) []int {
	if root == nil {
		return []int{}
	}

	hdNodeMap := make(map[int]int) // map hd to node value
	queue := list.New()
	type Pair struct {
		node *Node
		hd   int
	}

	queue.PushBack(Pair{root, 0})

	minHd, maxHd := 0, 0

	for queue.Len() > 0 {
		front := queue.Front()
		queue.Remove(front)
		pair := front.Value.(Pair)
		node, hd := pair.node, pair.hd

		hdNodeMap[hd] = node.Val // overwrite to keep bottom-most node

		if hd < minHd {
			minHd = hd
		}
		if hd > maxHd {
			maxHd = hd
		}

		if node.Left != nil {
			queue.PushBack(Pair{node.Left, hd - 1}) // go left: hd - 1
		}
		if node.Right != nil {
			queue.PushBack(Pair{node.Right, hd + 1}) // go right: hd + 1
		}
	}

	result := []int{}
	for hd := minHd; hd <= maxHd; hd++ {
		result = append(result, hdNodeMap[hd])
	}
	return result
}

func main() {
	root := &Node{20, nil, nil}
	root.Left = &Node{8, nil, nil}
	root.Right = &Node{22, nil, nil}
	root.Left.Left = &Node{5, nil, nil}
	root.Left.Right = &Node{3, nil, nil}
	root.Left.Right.Left = &Node{10, nil, nil}
	root.Left.Right.Right = &Node{14, nil, nil}
	root.Right.Right = &Node{25, nil, nil}

	bv := bottomView(root)
	for i, val := range bv {
		if i > 0 {
			fmt.Print(" -> ")
		}
		fmt.Print(val)
	}
	fmt.Println(" -> null")
}

hdNodeMap[hd] = node.Val // overwrite to keep bottom-most node

update map with current node value at horizontal distance, overwriting previous to keep bottom node

if node.Left != nil { queue.PushBack(Pair{node.Left, hd - 1}) // go left: hd - 1 }

enqueue left child with hd decreased by 1 to track vertical position

if node.Right != nil { queue.PushBack(Pair{node.Right, hd + 1}) // go right: hd + 1 }

enqueue right child with hd increased by 1 to track vertical position

for hd := minHd; hd <= maxHd; hd++ { result = append(result, hdNodeMap[hd]) }

collect bottom view nodes from leftmost to rightmost horizontal distance

Output

5 -> 10 -> 3 -> 14 -> 25 -> null

Complexity Analysis

Time: O(n) because we visit each node once in a breadth-first manner

Space: O(n) because we store nodes in the queue and map for all horizontal distances

vs Alternative: Compared to a naive approach that might do multiple traversals or store all nodes per vertical line, this approach is efficient with a single BFS and overwriting map entries

Edge Cases

Empty tree

Returns empty list since there are no nodes

DSA Go

if root == nil {
	return []int{}
}

Single node tree

Returns list with only that node's value

DSA Go

hdNodeMap[hd] = node.Val // overwrite to keep bottom-most node

All nodes aligned to left

Bottom view shows all nodes as they have distinct horizontal distances

DSA Go

queue.PushBack(Pair{node.Left, hd - 1})

When to Use This Pattern

When asked to find nodes visible from the bottom or side of a tree, use horizontal distance tracking with BFS to capture the 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 a horizontal distance when visiting a node to keep the bottom-most node

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

The key is to overwrite nodes at the same horizontal distance during a level order traversal to keep the bottom-most node.