Why Bottom View of Binary Tree in DSA Go?

The Big Idea

Discover how to see the hidden parts of a tree from below without guessing!

The Scenario

Imagine you have a tall tree in your backyard and you want to see which branches are visible if you look at it from the bottom. You try to write down all the branches you see from the ground, but the tree is so big and complex that it's hard to keep track of which branches hide others.

The Problem

Trying to figure out the bottom view by looking at the tree manually or by checking each branch one by one is slow and confusing. You might miss some branches or count the wrong ones because some branches overlap when seen from below.

The Solution

The bottom view of a binary tree helps you find exactly which nodes (branches) are visible from the bottom by using a smart way to track their positions. It uses horizontal distances and levels to pick the right nodes, so you don't have to guess or check everything manually.

Before vs After

✗ Before

func bottomViewManual(root *Node) {
    // Manually check each node and guess visibility
    // This is slow and error-prone
}

✓ After

func bottomView(root *Node) []int {
    // Use horizontal distance and level to find bottom view
    // Efficient and accurate
}

What It Enables

This concept lets you quickly and correctly find which parts of a tree are visible from the bottom, even for large and complex trees.

Real Life Example

In city planning, if you want to know which buildings are visible from the street level when looking up, bottom view logic helps decide which buildings block others.

Key Takeaways

Manual checking of tree visibility is confusing and slow.

Bottom view uses horizontal distance and levels to find visible nodes.

This method is fast, accurate, and works for any tree size.

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