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.