Bottom View of Binary Tree in DSA Go - Build from Scratch

Bottom View of Binary Tree

📖 Scenario: You are working on a program that helps visualize a binary tree from different perspectives. One useful view is the bottom view, which shows the nodes visible when the tree is seen from the bottom.Imagine standing under a tree and looking up. The bottom view shows the nodes that you can see without any other nodes blocking them vertically.

🎯 Goal: Build a Go program that computes the bottom view of a binary tree. The program will create a binary tree, assign horizontal distances to nodes, and then print the bottom view nodes from left to right.

📋 What You'll Learn

Create a binary tree with the exact structure given

Use a map to track the bottom-most node at each horizontal distance

Traverse the tree using level order traversal with horizontal distances

Print the bottom view nodes in order from leftmost to rightmost horizontal distance

💡 Why This Matters

🌍 Real World

Bottom view of a binary tree is useful in graphical applications, network routing visualization, and understanding hierarchical data from different perspectives.

💼 Career

Understanding tree traversals and views is important for software engineers working with data structures, algorithms, and system design.

1

Create the Binary Tree Structure

Create a binary tree with the exact structure below using a Node struct with data int, left *Node, and right *Node. The tree nodes and their values are:
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.left = &Node{data: 4}
root.right.right = &Node{data: 25}
root.left.right.left = &Node{data: 10}
root.left.right.right = &Node{data: 14}

DSA Go

package main

import "fmt"

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

func main() {
    // Create the binary tree nodes as described
    // Your code here
}

Hint

Define the Node struct first. Then create the root node and assign its left and right children exactly as given.

2

Set Up Data Structures for Bottom View

Create a map called hdNodeMap of type map[int]int to store the bottom-most node's data for each horizontal distance. Also, create a queue slice called queue to hold pairs of *Node and their horizontal distance as int. Initialize the queue with the root node and horizontal distance 0.

DSA Go

package main

import "fmt"

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

type Pair struct {
    node *Node
    hd   int
}

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.left = &Node{data: 4}
    root.right.right = &Node{data: 25}
    root.left.right.left = &Node{data: 10}
    root.left.right.right = &Node{data: 14}

    // Create hdNodeMap and queue with root and hd=0
    // Your code here
}

Hint

Use a map with int keys and int values to store node data by horizontal distance. Use a slice of Pair structs to hold nodes and their horizontal distances.

3

Traverse Tree and Update Bottom View Map

Use a for loop to process the queue until it is empty. In each iteration, dequeue the first element, update hdNodeMap with the node's data for its horizontal distance, then enqueue the left child with horizontal distance -1 and right child with horizontal distance +1 if they exist.

DSA Go

package main

import "fmt"

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

type Pair struct {
    node *Node
    hd   int
}

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.left = &Node{data: 4}
    root.right.right = &Node{data: 25}
    root.left.right.left = &Node{data: 10}
    root.left.right.right = &Node{data: 14}

    hdNodeMap := make(map[int]int)
    queue := []Pair{{node: root, hd: 0}}

    // Traverse the tree and update hdNodeMap
    // Your code here
}

Hint

Use a queue to do level order traversal. Update the map with the current node's data for its horizontal distance. Add children to the queue with updated horizontal distances.

4

Print the Bottom View from Left to Right

Find the minimum and maximum horizontal distances from hdNodeMap. Then use a for loop from minimum to maximum horizontal distance to print the node data stored in hdNodeMap separated by spaces.

DSA Go

package main

import "fmt"

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

type Pair struct {
    node *Node
    hd   int
}

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.left = &Node{data: 4}
    root.right.right = &Node{data: 25}
    root.left.right.left = &Node{data: 10}
    root.left.right.right = &Node{data: 14}

    hdNodeMap := make(map[int]int)
    queue := []Pair{{node: root, hd: 0}}

    for len(queue) > 0 {
        currPair := queue[0]
        queue = queue[1:]

        hdNodeMap[currPair.hd] = currPair.node.data

        if currPair.node.left != nil {
            queue = append(queue, Pair{node: currPair.node.left, hd: currPair.hd - 1})
        }
        if currPair.node.right != nil {
            queue = append(queue, Pair{node: currPair.node.right, hd: currPair.hd + 1})
        }
    }

    // Print bottom view nodes from left to right
    // Your code here
}

Hint

Find the smallest and largest horizontal distances in the map. Then print the node data in order from smallest to largest horizontal distance separated by spaces.

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