Bottom View of Binary Tree in DSA Go - Deep Dive

Overview - Bottom View of Binary Tree

What is it?

The bottom view of a binary tree shows the nodes visible when the tree is seen from the bottom. It means for each vertical line of nodes, we see the node that is the lowest or deepest in the tree. This view helps us understand the structure of the tree from a different angle. It is different from the top view, which shows the highest nodes on each vertical line.

Why it matters

Without the bottom view concept, we would miss understanding how nodes overlap vertically in a tree. It helps in visualizing and solving problems related to vertical order traversal and visibility in trees. This is useful in graphics, network routing, and hierarchical data representation where the lowest visible elements matter. Without it, many tree-based problems would be harder to solve or visualize.

Where it fits

Before learning bottom view, you should understand binary trees, tree traversal methods, and the concept of horizontal distance in trees. After mastering bottom view, you can explore related views like top view, vertical order traversal, and advanced tree problems involving visibility and layering.

Mental Model

Core Idea

The bottom view of a binary tree is the set of nodes visible when looking straight up from below, showing the lowest node at each vertical position.

Think of it like...

Imagine standing under a forest looking up at tree trunks. You only see the trunks that are closest to the ground at each horizontal position because taller trunks behind them are hidden.

          (20)
         /    \
     (8)       (22)
    /   \         \
 (5)    (3)       (25)
        /   \      \
      (10)  (14)   (30)

Horizontal distances (HD):
HD -2: 5
HD -1: 10
HD  0: 3 (lowest at vertical 0)
HD  1: 14
HD  2: 25
HD  3: 30

Bottom view: 5 -> 10 -> 3 -> 14 -> 25 -> 30

Build-Up - 6 Steps

1

Foundation

Understanding Binary Trees Basics

Concept: Learn what a binary tree is and how nodes are connected.

A binary tree is a structure where each node has up to two children: left and right. The top node is called the root. Nodes below are called children, and nodes without children are leaves. We can traverse the tree in different orders like preorder, inorder, and postorder to visit nodes.

Result

You can represent and traverse any binary tree structure.

Understanding the basic structure of binary trees is essential before exploring views like bottom view.

2

Foundation

Horizontal Distance Concept in Trees

Concept: Introduce horizontal distance (HD) to locate nodes vertically.

Assign HD=0 to the root. For left child, HD = parent's HD - 1. For right child, HD = parent's HD + 1. This helps group nodes vertically. Nodes with the same HD lie on the same vertical line.

Result

You can map each node to a vertical line using HD.

Horizontal distance is the key to grouping nodes for bottom view calculation.

3

Intermediate

Tracking Node Depth for Bottom View

Concept: Use node depth to decide which node is visible from bottom at each HD.

While traversing, keep track of each node's depth (distance from root). For each HD, store the node with the greatest depth because it will be visible from the bottom. If a new node at the same HD has greater depth, update the stored node.

Result

You can identify the lowest node at each vertical line.

Depth comparison ensures the bottom-most node is chosen for each vertical line.

4

Intermediate

Using Level Order Traversal for Bottom View

🤔Before reading on: do you think depth-first or breadth-first traversal is better for bottom view? Commit to your answer.

Concept: Level order traversal (breadth-first) helps process nodes level by level, making it easier to track depth and update bottom view nodes.

Perform a level order traversal using a queue. For each node, record its HD and depth. Update the map of HD to node if current node is deeper or first at that HD. This approach naturally processes nodes from top to bottom.

Result

Bottom view nodes are correctly identified after one traversal.

Level order traversal aligns with depth tracking, simplifying bottom view computation.

5

Advanced

Implementing Bottom View in Go

🤔Before reading on: do you think a map or slice is better to store HD-node pairs? Commit to your answer.

Concept: Use a map to store HD to node data and a queue for level order traversal in Go.

package main import ( "fmt" ) type Node struct { Val int Left *Node Right *Node } type QueueItem struct { Node *Node HD int Depth int } func bottomView(root *Node) []int { if root == nil { return []int{} } queue := []QueueItem{{root, 0, 0}} hdMap := map[int]QueueItem{} minHD, maxHD := 0, 0 for len(queue) > 0 { item := queue[0] queue = queue[1:] // Update map if deeper or first node at HD if existing, ok := hdMap[item.HD]; !ok || item.Depth >= existing.Depth { hdMap[item.HD] = item } if item.HD < minHD { minHD = item.HD } if item.HD > maxHD { maxHD = item.HD } if item.Node.Left != nil { queue = append(queue, QueueItem{item.Node.Left, item.HD - 1, item.Depth + 1}) } if item.Node.Right != nil { queue = append(queue, QueueItem{item.Node.Right, item.HD + 1, item.Depth + 1}) } } result := []int{} for hd := minHD; hd <= maxHD; hd++ { result = append(result, hdMap[hd].Node.Val) } 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.Right.Right = &Node{25, nil, nil} root.Left.Right.Left = &Node{10, nil, nil} root.Left.Right.Right = &Node{14, nil, nil} root.Right.Right.Right = &Node{30, nil, nil} fmt.Println(bottomView(root)) }

Result

[5 10 3 14 25 30]

Implementing bottom view with a map and queue in Go efficiently tracks nodes by HD and depth.

6

Expert

Handling Edge Cases and Optimizations

🤔Before reading on: do you think nodes at the same depth but different insertion order affect bottom view? Commit to your answer.

Concept: Consider cases with multiple nodes at same HD and depth, and optimize memory by using minimal data structures.

In cases where nodes share the same HD and depth, the last processed node in level order traversal is chosen. This is because level order processes nodes left to right at each level. To optimize, store only necessary info (node value and depth) in the map. Also, avoid storing entire nodes if memory is a concern.

Result

Bottom view is consistent and memory usage is efficient.

Understanding traversal order and data storage choices prevents subtle bugs and improves performance.

Under the Hood

The algorithm uses a breadth-first search (level order traversal) to visit nodes level by level. Each node is assigned a horizontal distance (HD) from the root. A map stores the deepest node found so far at each HD. When a node at the same HD but greater depth is found, it replaces the previous node in the map. After traversal, the map entries sorted by HD give the bottom view.

Why designed this way?

Level order traversal naturally processes nodes by increasing depth, making it easy to track the lowest node at each HD. Using a map keyed by HD allows quick updates and lookups. Alternatives like depth-first search complicate depth tracking and may require extra bookkeeping. This design balances simplicity and efficiency.

┌───────────────┐
│   Start root  │
└──────┬────────┘
       │ HD=0, Depth=0
       ▼
┌───────────────┐
│ Enqueue root  │
└──────┬────────┘
       │
       ▼
┌─────────────────────────────┐
│ While queue not empty:       │
│  Dequeue node               │
│  Update map if deeper node  │
│  Enqueue left child (HD-1) │
│  Enqueue right child (HD+1)│
└─────────────┬───────────────┘
              │
              ▼
┌─────────────────────────────┐
│ After traversal:             │
│ Map contains bottom nodes    │
│ Sort map by HD and output   │
└─────────────────────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does the bottom view always include the deepest node in the entire tree? Commit yes or no.

Common Belief: The bottom view shows the deepest node in the whole tree.

Reality: The bottom view shows the deepest node at each vertical line (horizontal distance), not the single deepest node overall.

Why it matters: Confusing this leads to incorrect results by missing nodes visible at other vertical lines.

Quick: Can a node with a smaller depth ever appear in the bottom view over a deeper node at the same horizontal distance? Commit yes or no.

Common Belief: A node closer to the root can appear in the bottom view over a deeper node at the same horizontal distance.

Reality: The bottom view always shows the node with the greatest depth at each horizontal distance, so deeper nodes replace shallower ones.

Why it matters: Misunderstanding this causes incorrect node selection and wrong bottom view output.

Quick: Is depth-first traversal a good approach to compute bottom view? Commit yes or no.

Common Belief: Depth-first traversal is suitable for bottom view calculation.

Reality: Depth-first traversal complicates tracking the lowest nodes by depth and horizontal distance; level order traversal is better suited.

Why it matters: Using depth-first can lead to complex code and bugs in determining the correct bottom view.

Quick: Does the bottom view always match the leaf nodes of the tree? Commit yes or no.

Common Belief: Bottom view nodes are always leaf nodes.

Reality: Bottom view nodes can be internal nodes if they are the lowest visible nodes at their horizontal distance.

Why it matters: Assuming only leaves appear in bottom view causes missing important nodes and incorrect visualization.

Expert Zone

1

The order of processing nodes at the same depth and horizontal distance affects which node appears in the bottom view, especially in trees with multiple nodes aligned vertically.

2

Memory optimization can be achieved by storing only node values and depths instead of full node pointers in the map, which is important in large trees.

3

In some variations, bottom view can be extended to weighted trees or graphs, requiring adaptations of the horizontal distance concept.

When NOT to use

Bottom view is not suitable when you need the top view or full vertical order traversal with all nodes. For those, use top view algorithms or vertical order traversal methods that collect all nodes per vertical line.

Production Patterns

Bottom view is used in graphical rendering engines to determine visible elements from a viewpoint, in network routing to visualize hierarchical paths, and in database indexing to represent hierarchical data summaries.

Connections

Top View of Binary Tree

Opposite vertical visibility concept; top view shows highest nodes, bottom view shows lowest nodes at each vertical line.

Understanding bottom view clarifies how vertical visibility changes with perspective, helping grasp top view and vertical order traversal.

Breadth-First Search (BFS)

Bottom view algorithm uses BFS to traverse nodes level by level, tracking depth and horizontal distance.

Knowing BFS deeply helps implement bottom view efficiently and understand why level order traversal suits this problem.

Urban Planning and Skyline Problem

Both involve viewing structures from a side or bottom perspective to determine visible elements in overlapping vertical lines.

Recognizing this connection shows how bottom view algorithms relate to real-world problems like city skyline visualization.

Common Pitfalls

#1 Ignoring horizontal distance and only tracking depth leads to wrong bottom view.

Wrong approach:

func bottomView(root *Node) []int {
// Just traverse and print deepest node
// No horizontal distance tracking
return []int{root.Val}
}

Correct approach:

func bottomView(root *Node) []int {
// Use map with horizontal distance and depth
// Traverse level order
// Update map with deepest node per HD
return []int{...}
}

Root cause:

Not understanding that horizontal distance groups nodes vertically, which is essential for bottom view.

#2 Using depth-first traversal without tracking depth and HD properly causes incorrect node selection.

Wrong approach:

func bottomView(root *Node) []int {
// DFS traversal without depth or HD tracking
return []int{...}
}

Correct approach:

func bottomView(root *Node) []int {
// Use BFS with queue tracking HD and depth
return []int{...}
}

Root cause:

Misunderstanding traversal method suitability for bottom view calculation.

#3 Assuming bottom view nodes are always leaves and skipping internal nodes.

Wrong approach:

func bottomView(root *Node) []int {
// Only collect leaf nodes
return []int{...}
}

Correct approach:

func bottomView(root *Node) []int {
// Collect nodes with greatest depth per HD, leaf or internal
return []int{...}
}

Root cause:

Incorrect assumption about which nodes appear in bottom view.

Key Takeaways

Bottom view shows the lowest node visible at each vertical line of a binary tree when viewed from below.

Horizontal distance groups nodes vertically and is essential to compute bottom view correctly.

Level order traversal is the best method to track nodes by depth and horizontal distance for bottom view.

The bottom view can include internal nodes, not just leaves, depending on their position and depth.

Understanding bottom view helps solve related problems like top view and vertical order traversal.

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