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.