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.

Practice

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

easy

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

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

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

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

Solution

1. Step 1: Understand the bottom view concept

   The bottom view shows nodes that are visible when looking at the tree from below, ignoring nodes hidden behind others.

2. Step 2: Compare with other views

   Top view shows nodes from above, left view from left side, right view from right side. Bottom view is unique for the bottom perspective.

3. Final Answer:

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

4. Quick Check:

   Bottom view = Nodes visible from bottom [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 data structure is commonly used to track nodes and their horizontal distances when computing the bottom view of a binary tree in Go?

easy

A. Stack

B. Queue

C. Map (dictionary)

D. Slice

Solution

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

   To find bottom view, we track nodes by their horizontal distance from root, so we need a structure to map distance to node value.

2. Step 2: Choose the correct data structure

   A map (dictionary) stores key-value pairs, perfect for horizontal distance as key and node value as value.

3. Final Answer:

   Map (dictionary) -> Option C

4. Quick Check:

   Use map to store horizontal distance -> node [OK]

Hint: Use map to link horizontal distance with node value [OK]

Common Mistakes:

• Using stack which is LIFO, not suitable here
• Using queue only for traversal, not for mapping
• Using slice without keys for horizontal distance

3. Given the binary tree below, what is the bottom view output?

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

medium

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

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

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

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

Solution

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

   Assign horizontal distances (HD) starting from root (20) as 0. Left child decreases HD by 1, right child increases by 1. - 20 (HD=0) - 8 (HD=-1), 22 (HD=1) - 5 (HD=-2), 3 (HD=0), 25 (HD=2) - 10 (HD=-1), 14 (HD=1)

2. Step 2: Determine bottom view nodes by last node at each HD

   At HD=-2: 5 HD=-1: 10 (overwrites 8) HD=0: 3 (overwrites 20) HD=1: 14 (overwrites 22) HD=2: 25 Bottom view = [5, 10, 3, 14, 25]

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Taking first node at HD instead of last
• Mixing horizontal distances
• Ignoring nodes on right side

4. Consider this Go code snippet for bottom view. What is the error?

func bottomView(root *Node) []int {
    if root == nil {
        return nil
    }
    queue := []*Node{root}
    hdMap := make(map[int]int)
    hd := 0
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        hdMap[hd] = node.val
        if node.left != nil {
            queue = append(queue, node.left)
            hd--
        }
        if node.right != nil {
            queue = append(queue, node.right)
            hd++
        }
    }
    // code to extract and return bottom view omitted
    return nil
}

medium

A. Queue is not initialized properly

B. Function returns nil instead of bottom view slice

C. Map is declared with wrong type

D. Horizontal distance (hd) is not tracked per node, causing wrong mapping

Solution

1. Step 1: Analyze horizontal distance tracking

   The variable hd is a single integer updated globally, but each node can have different hd. It should be tracked per node, e.g., by storing node and hd together in queue.

2. Step 2: Identify impact of error

   Because hd is not per node, hdMap updates will be incorrect, leading to wrong bottom view.

3. Final Answer:

   Horizontal distance (hd) is not tracked per node, causing wrong mapping -> Option D

4. Quick Check:

   Track hd per node, not globally [OK]

Hint: Track horizontal distance with each node in queue [OK]

Common Mistakes:

• Updating hd globally instead of per node
• Ignoring nil root check
• Returning nil without result

5. You want to print the bottom view of a binary tree but only for nodes with horizontal distance between -1 and 1 inclusive. How would you modify the standard bottom view algorithm to achieve this?

hard

A. Store all nodes in map, then filter keys between -1 and 1 before printing

B. Ignore nodes outside horizontal distance range during traversal

C. Use a stack instead of queue for traversal

D. Traverse tree in preorder and print nodes with hd between -1 and 1

Solution

1. Step 1: Understand the requirement

   To correctly get bottom view for hd [-1,1], must visit entire tree as in-range hd nodes may be reached via out-of-range parents.

2. Step 2: Standard traversal with filtered output

   Run standard level order, update map for all hd. When printing, iterate only over keys -1 to 1 in sorted order.

3. Final Answer:

   Store all nodes in map, then filter keys between -1 and 1 before printing -> Option A

4. Quick Check:

   Traverse all, map all hd, print filtered keys [OK]

Hint: Traverse all nodes, filter map keys when printing [OK]

Common Mistakes:

• Ignoring out-of-range nodes during traversal misses deeper in-range nodes
• Using stack breaks level order
• Preorder traversal disrupts bottom view order