Bottom View of Binary Tree in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bottom View for a Simple Binary Tree

What is the bottom view of the following binary tree after running the given code?

DSA Go

package main

import "fmt"

type Node struct {
    data  int
    left  *Node
    right *Node
}

func bottomView(root *Node) []int {
    if root == nil {
        return []int{}
    }
    type pair struct {
        node *Node
        hd   int
    }
    queue := []pair{{root, 0}}
    hdMap := map[int]int{}
    minHd, maxHd := 0, 0

    for len(queue) > 0 {
        p := queue[0]
        queue = queue[1:]
        hdMap[p.hd] = p.node.data
        if p.hd < minHd {
            minHd = p.hd
        }
        if p.hd > maxHd {
            maxHd = p.hd
        }
        if p.node.left != nil {
            queue = append(queue, pair{p.node.left, p.hd - 1})
        }
        if p.node.right != nil {
            queue = append(queue, pair{p.node.right, p.hd + 1})
        }
    }

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

func main() {
    root := &Node{data: 20}
    root.left = &Node{data: 8}
    root.right = &Node{data: 22}
    root.left.left = &Node{data: 5}
    root.left.right = &Node{data: 3}
    root.right.right = &Node{data: 25}
    root.left.right.left = &Node{data: 10}
    root.left.right.right = &Node{data: 14}

    fmt.Println(bottomView(root))
}

A [5, 8, 3, 14, 25]

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

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

D [8, 10, 3, 14, 22]

💡 Hint

Remember, bottom view shows the last node at each horizontal distance when viewed from bottom.

The bottom view is computed by tracking the horizontal distance (hd) of each node from the root. The last node encountered at each hd during level order traversal is stored. For this tree, the bottom nodes at hd -2 to 2 are 5, 10, 3, 14, and 25 respectively.

🧠 Conceptual

intermediate

Understanding Horizontal Distance in Bottom View

In the bottom view of a binary tree, what does the horizontal distance (hd) represent?

A The distance of the node from the root node horizontally, with root at 0, left child hd-1, right child hd+1

B The vertical level of the node in the tree

C The depth of the node from the root

D The number of nodes in the subtree rooted at the node

💡 Hint

Think about how nodes are positioned left or right relative to the root.

Horizontal distance is a measure of how far left or right a node is from the root. The root has hd 0, left child decreases hd by 1, right child increases hd by 1.

🔧 Debug

advanced

Identify the Error in Bottom View Implementation

What error will occur if the line 'hdMap[p.hd] = p.node.data' is moved after the checks for minHd and maxHd in the code below?

DSA Go

for len(queue) > 0 {
    p := queue[0]
    queue = queue[1:]
    if p.hd < minHd {
        minHd = p.hd
    }
    if p.hd > maxHd {
        maxHd = p.hd
    }
    hdMap[p.hd] = p.node.data
    if p.node.left != nil {
        queue = append(queue, pair{p.node.left, p.hd - 1})
    }
    if p.node.right != nil {
        queue = append(queue, pair{p.node.right, p.hd + 1})
    }
}

A No error; code runs correctly with same output

B Runtime panic due to nil map access

C Incorrect bottom view output because minHd and maxHd are not updated before map assignment

D Compilation error due to variable scope

💡 Hint

Consider the order of updating minHd, maxHd, and map assignment.

Moving the map assignment after minHd and maxHd updates does not cause any error or change output. The map assignment and min/max updates are independent and order does not affect correctness.

❓ Predict Output

advanced

Bottom View Output for a Skewed Binary Tree

What is the output of the bottom view function for the following skewed binary tree?

DSA Go

package main

import "fmt"

type Node struct {
    data  int
    left  *Node
    right *Node
}

func bottomView(root *Node) []int {
    if root == nil {
        return []int{}
    }
    type pair struct {
        node *Node
        hd   int
    }
    queue := []pair{{root, 0}}
    hdMap := map[int]int{}
    minHd, maxHd := 0, 0

    for len(queue) > 0 {
        p := queue[0]
        queue = queue[1:]
        hdMap[p.hd] = p.node.data
        if p.hd < minHd {
            minHd = p.hd
        }
        if p.hd > maxHd {
            maxHd = p.hd
        }
        if p.node.left != nil {
            queue = append(queue, pair{p.node.left, p.hd - 1})
        }
        if p.node.right != nil {
            queue = append(queue, pair{p.node.right, p.hd + 1})
        }
    }

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

func main() {
    root := &Node{data: 1}
    root.right = &Node{data: 2}
    root.right.right = &Node{data: 3}
    root.right.right.right = &Node{data: 4}
    root.right.right.right.right = &Node{data: 5}

    fmt.Println(bottomView(root))
}

A [1, 3, 5]

B [5]

C [1]

D [1, 2, 3, 4, 5]

💡 Hint

In a right skewed tree, each node has a unique horizontal distance.

Each node is to the right of the previous, so horizontal distances increase from 0 to 4. Bottom view includes all nodes in order.

🚀 Application

expert

Number of Nodes in Bottom View for a Complex Tree

Given a binary tree with the structure below, how many nodes will be in its bottom view?

DSA Go

/* Tree structure:
          15
         /  \
       10    20
      /  \     \
     8   12     25
      \         /
      9       22
*/

A 5

B 7

C 6

D 4

💡 Hint

Count unique horizontal distances covered by bottom nodes.

Horizontal distances and bottom nodes are: - hd -2: 8 - hd -1: 9 - hd 0: 12 - hd 1: 22 - hd 2: 25 - hd 0 also has 15 and 10 but bottom view keeps last at hd 0 which is 12 So total unique hd with bottom nodes are 6.

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